Searching for close alternative plans |
| |
Authors: | Ariel Felner Roni Stern Jeffrey S Rosenschein Alex Pomeransky |
| |
Affiliation: | (1) Department of Information Systems Engineering, Ben-Gurion University, Beer-Sheva, Israel;(2) School of Engineering and Computer Science, Hebrew University, Jerusalem, Israel;(3) Department of Computer Science, Bar Ilan University, Ramat Gan, Israel |
| |
Abstract: | Consider the situation where an intelligent agent accepts as input a complete plan, i.e., a sequence of states (or operators)
that should be followed in order to achieve a goal. For some reason, the given plan cannot be implemented by the agent, who
then goes about trying to find an alternative plan that is as close as possible to the original. To achieve this, a search
algorithm that will find similar alternative plans is required, as well as some sort of comparison function that will determine
which alternative plan is closest to the original. In this paper, we define a number of distance metrics between plans, and characterize these functions and their respective attributes and advantages. We then develop a general
algorithm based on best-first search that helps an agent efficiently find the most suitable alternative plan. We also propose
a number of heuristics for the cost function of this best-first search algorithm. To explore the generality of our idea, we
provide three different problem domains where our approach is applicable: physical roadmap path finding, the blocks world,
and task scheduling. Experimental results on these various domains support the efficiency of our algorithm for finding close
alternative plans.
A preliminary version of this paper appeared in the International Joint Conference on Autonomous Agents and Multiagent Systems
(8).
An erratum to this article can be found at |
| |
Keywords: | Best-first search Shortest path Scheduling Replanning Rescheduling |
本文献已被 SpringerLink 等数据库收录! |
|