Analogical Replay for Efficient Conditional Planning

Abstract

Recently, several planners have been designed that can create conditionally branching plans to solve problems whichinvolve uncertainty. These planners represent an important step in broadening the applicabilityof AI planning techniques, but they typically must search a larger space than non-branching planners, since they must produce valid plans for each branch considered. In the worst case this can produce an exponential increase in the complexity of planning. If conditional planners are to become usable in real-world domains, this complexitymust be controlled by sharing planning e#ort among branches. Analogical plan reuse should play a fundamental role in this process. We have implemented a conditional probabilistic planner that uses analogical plan replay to derive the maximum bene#t from previously solved branches of the plan. This approach provides valuable guidance for when and how to merge di#erent branches of the plan and exploits the high similaritybetween th...