Moving Target Search with Intelligence

Toru Ishida

We previously proposed the moving target search (MTS) algorithm, where the location of the goal may change during the course of the search. MTS is the first search algorithm concerned with problem solving in a dynamically changing environment. However, since we constructed the algorithm with the minimum operations necessary for guaranteeing its completeness, the algorithm as proposed is neither efficient nor intelligent. In this paper, we introduce innovative notions created in the area of resource- bounded planning into the formal search algorithm, MTS. Our goal is to improve the efficiency of MTS, while retaining its completeness. Notions that are introduced are (1) commitment to goals, and (2) deliberation for selecting plans. Evaluation results demonstrate that the intelligent MTS is 10 to 20 times more efficient than the original MTS in uncertain situations.

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.