Position paper: Incremental search algorithms considered poorly understood

摘要: Incremental search algorithms, such as D* Lite, reuse information from previous searches to speed up the current and can thus solve sequences of similar problems faster than Repeated A*, which performs repeated A* searches. In this position paper, we study goal-directed navigation in initially unknown terrain point out that it is currently not well understood when Lite runs A*. general, appears for easy (where agent reaches goal with only a small number searches), means quite often practice. We draw two conclusions, namely incremental algorithms need be evaluated more diverse testbeds improve our understanding their properties they improved competitive problems. freespace assumption terrain, needed robotics video games. The discretized into grid known dimensions. does know cells are blocked but always observes blockage status neighboring its cell adds them map. It then move any unblocked cell. moves given coordinates using following strategy: finds shortest (unblocked) path If exist, stops unsuccessfully. Otherwise, follows until either cell, case successfully, or blocked, repeats process. needs sequence fast. (Koenig Likhachev 2005), search. claim ∗Our research was supported by NSF, ARO ONR grants Sven Koenig (while he served at NSF) Fondecyt grant Jorge Baier. Copyright c © 2012, Association Advancement Artificial Intelligence (www.aaai.org). All rights reserved. Forward A*.1 For example, many cases, typically where times before (or discovers impossible). Examples gridworlds start close each other h-values misleading (including blocked). reason following: has advantage expands fewer Backward after first since reuses However, disadvantage during also slowly (Forward Backward) This an effect becomes pronounced further apart are. subsequent reach faster, see 2005) explanation. use version whenever on (as most evaluations do), different evaluation breaks ties among same f-value favor smaller g-values opposite direction because a) b) f-values pairs rather triples. 159 Proceedings Fifth Annual Symposium Combinatorial Search