Search |  Contact |  SRI Home Do not follow this link, or your host will be blocked from this site. This is a spider trap. Do not follow this link, or your host will be blocked from this site. This is a spider trap. Do not follow this link, or your host will be blocked from this site. This is a spider trap.A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A ASRI International.  333 Ravenswood Avenue.  Menlo Park, CA 94025-3493. SRI International is a nonprofit corporation.

AIC Seminar Series

Navigating in Planning Search Spaces: why it is useful to have a backbone

Blazej BulkaAritificial Intelligence Center, SRI International

Date:  2007-08-23 at 16:00

Location:  EJ228 (SRI E building)  (Directions)

   Abstract

In a classical automated planning setting, a planner is given information about the current state of the world, the definitions of available actions, and a set of goals that should be achieved. The planner’s task is to determine which actions will lead to the accomplishment of the goals. A planner may be created to reason for only a single domain (domain-dependent planner; e.g., a planner that is designed solely to create an itinerary for air travel) or for a whole class of domains (domain-independent planner). Although domain-independent planners are more flexible than domain-dependent ones, they are also slower than domain-dependent planners, which use specialized algorithms. One of the reasons for this difference is that these algorithms already embed the result of human reasoning and analysis of the problem (e.g., finding recurring patterns within the problem or discovering similarities to another known problem). Enabling domain-independent planners to perform this type of reasoning themselves may lead to significant performance improvements.

I propose to use previous experience and proactive analysis to create a planning backbone, which is a library of plans based on the topology of the underlying structure of the domain and other features of the search space. To enable the construction of the backbone, I identify a number of features that can be used to characterize search spaces and state spaces. Particular attention is given to topological features, which provide important information about the internal structure and patterns within the problem. Although domain-independent planners can plan in multiple domains, in practice, they are typically used to produce many plans in any given domain. Therefore, the proposed solution will be efficient, because the additional computational cost can be amortized across multiple planning episodes in the same domain.

   On-line Resources