Estimated-regression planning for interactions with web services
Drew McDermott · 2002
“Web services ” are agents on the web that provide services to other agents. Interacting with a web service is essen-tially a planning problem, provided the service exposes an interface containing action definitions, which in fact is an el-egant representation of how web services actually behave. The question is what sort of planner is best suited for solv-ing the resulting problems, given that dealing with web ser-vices involves gathering information and then acting on it. Estimated-regression planners use a backward analysis of the difficulty of a goal to guide a forward search through situa-tion space. They are well suited to the web-services domain because it is easy to relax the assumption of complete knowl-edge, and to formalize what it is they don’t know and could find out by sending the relevant messages. Applying them to this domain requires extending classical notations (e.g., PDDL) in various ways. A preliminary implementation of these ideas has been constructed, and further tests are under-way. The Solution and the Problem Estimated-regression planning is the name given to a family of planners including Unpop (McDermott 1996; 1999) and HSP (Bonet, Loerincs, & Geffner 1997; Bonet & Geffner 2001), in which situation-space search is guided by a heuris-tic estimator obtained by backward chaining in a “relaxed” problem space. Typically the relaxation neglects interac-tions, both constructive and destructive, between actions that achieve goals, and in particular neglects deletions com-pletely. The resulting space is so much smaller than situation space that a planner can build complete representation of it, called a regression graph. The regression graph reveals, for each conjunct of a goal, the minimal sequence of actions that could achieve it.1 Estimated-regression planners have been applied to classical-planning domains, those in which perfect informa-∗This work was supported by DARPA/DAML under contract number F30602-00-2-0600. Copyright c © 2001, American Association for Artificial Intelli-