An Empirical Comparison of Incremental Search Algorithms for On-Line Planning

Contents

In on-line planning an agent executes a sequence of actions to maximise some time dependent objective criterion. Deciding which actions to execute takes time, which the agent must manage in order to maximise overall performance. This is the meta-control problem. Incremental search algorithms select actions incrementally based upon a guided partial search through the local space of possible solutions. Hence, by carefully controlling the local searches, the time spent making decisions can be managed. This short paper presents three incremental search algorithms proposed in the literature and compares their performance over a range of problem complexities and timeliness requirements.