Planning with constraints (MOLGEN: Part 1)

摘要

Hierarchical planners distinguish between important considerations and details. A hierarchical planner creates descriptions of abstract states and divides its planning task into subproblems for refining the abstract states. The abstract states enable it to focus on important considerations, thereby avoiding the burden of trying to deal with everything at once. In most practical planning problems, however, the subproblems interact. Without the ability to handle these interactions, hierarchical planners can deal effectively only with idealized cases where subproblems are independent and can be solved separately.This paper presents an approach to hierarchical planning, termed constraint posting, that uses constraints to represent the interactions between subproblems. Constraints are dynamically formulated and propagated during hierarchical planning, and used to coordinate the solutions of nearly independent subproblems. This is illustrated with a computer program, called MOLGEN, that plans gene-cloning experiments in molecular genetics.