Commencing Execution

Richard Goodwin

Real-time search algorithms interleave search with execution in order to accomplish a task ei~ciently. Deciding when to begin execution of the current best action is crucial for creating high a performance realtime search algorithm. This paper explores the question of when to commencexecution for an on-line search performed with limited computation. We ex- *mine Good’s ideslised algorithm for deciding when to begin execution and illustrate some of its llmltations. We then present a revised, idealised algorithm that removes some of these limitations. The revised algorithm has been used u s basis for an algorithm that makes on-the-fly decisions for a simplified robot courier tuk. Previous empirical results show that this new algorithm outperforms previously used alsorithms. In this paper, we show that the di~erence in performance is bounded by a ratio of two to one. We discuss the situations where this limit is approached and suggest that overlappins search with execution in these situations is most beneficial.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.