Efficient Optimal Search under Expensive Edge Cost Computation

Efficient Optimal Search under Expensive Edge Cost Computation

Masataro Asai, Akihiro Kishimoto, Adi Botea, Radu Marinescu, Elizabeth M. Daly, Spyros Kotoulas

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
Main track. Pages 4266-4272. https://doi.org/10.24963/ijcai.2017/596

Optimal heuristic search has been successful in many domains, including journey planning, route planning and puzzle solving. Existing work typically assumes that the cost of each action can easily be obtained. However, in many problems, the exact edge cost is expensive to compute. Existing search algorithms face a significant performance bottleneck, due to an excessive overhead associated with dynamically calculating exact edge costs. We present DEA*, an algorithm for problems with expensive edge cost computations. DEA* combines heuristic edge cost evaluations with delayed node expansions, reducing the number of exact edge computations. We formally prove that DEA* is optimal and it is efficient with respect to the number of exact edge cost computations. We empirically evaluate DEA* on multiple-worker routing problems where the exact edge cost is calculated by invoking an external multi-modal journey planning engine. The results demonstrate the effectiveness of our ideas in reducing the computational time and improving the solving ability. In addition, we show the advantages of DEA* in domain-independent planning, where we simulate that accurate edge costs are expensive to compute.
Keywords:
Planning and Scheduling: Search in Planning and Scheduling
Combinatorial & Heuristic Search: Heuristic Search