{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,7]],"date-time":"2024-08-07T07:36:21Z","timestamp":1723016181869},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017,8]]},"abstract":"<jats:p>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.\n\nWe 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.\n\nWe 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.<\/jats:p>","DOI":"10.24963\/ijcai.2017\/596","type":"proceedings-article","created":{"date-parts":[[2017,7,28]],"date-time":"2017-07-28T05:14:07Z","timestamp":1501218847000},"page":"4266-4272","source":"Crossref","is-referenced-by-count":0,"title":["Efficient Optimal Search under Expensive Edge Cost Computation"],"prefix":"10.24963","author":[{"given":"Masataro","family":"Asai","sequence":"first","affiliation":[{"name":"The University of Tokyo"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Akihiro","family":"Kishimoto","sequence":"additional","affiliation":[{"name":"IBM Research, Ireland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adi","family":"Botea","sequence":"additional","affiliation":[{"name":"IBM Research, Ireland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Radu","family":"Marinescu","sequence":"additional","affiliation":[{"name":"IBM Research, Ireland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Elizabeth","family":"M. Daly","sequence":"additional","affiliation":[{"name":"IBM Research, Ireland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Spyros","family":"Kotoulas","sequence":"additional","affiliation":[{"name":"IBM Research, Ireland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"10584","event":{"number":"26","sponsor":["International Joint Conferences on Artificial Intelligence Organization (IJCAI)","University of Technology Sydney (UTS)","Australian Computer Society (ACS)"],"acronym":"IJCAI-2017","name":"Twenty-Sixth International Joint Conference on Artificial Intelligence","start":{"date-parts":[[2017,8,19]]},"theme":"Artificial Intelligence","location":"Melbourne, Australia","end":{"date-parts":[[2017,8,26]]}},"container-title":["Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence"],"original-title":[],"deposited":{"date-parts":[[2017,7,28]],"date-time":"2017-07-28T07:54:42Z","timestamp":1501228482000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ijcai.org\/proceedings\/2017\/596"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2017,8]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/ijcai.2017\/596","relation":{},"subject":[],"published":{"date-parts":[[2017,8]]}}}