Incremental Search Algorithms for Real-time Decision Making

Wepropose incremental, real-time search as a general approach to real-time decision making. Wemodel real-time decision makingas incremental tree search with a limited numberof node expansions betweendecisions. Weshowthat the decision policy of moving towardthe best frontier node is not optimal, but nevertheless performsnearly as well as an expected-valuebased decision policy. Wealso showthat the real-time constraint causesdifficulties for traditional best-first search algorithms. Wethen present a new approach that uses a separate heuristic function for choosing where to explore and which decision to make. Empirical results for randomtrees showthat our newalgorithm outperformsthe traditional best-first search approach to real-time decision making, and that depthfirst branch-and-boundperforms nearly as well as the morecomplicatedbest-first variation.

Authors

• Joseph C. Pemberton
• Richard E. Korf

Keywords

No keywords are indexed for this paper.