Planning with Constraints. Planning Sub System.

Planning with Constraints

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, calledMOLGEN, that plans gene-cloning experiments in molecular genetics.

1. Introduction

Divide each problem that you examine into as many parts as you can and as you need to solve them more easily.

This rule of Descartes is of little use as long as the art of dividing. . . remains unexplained. . . . By dividing his problem into unsuit..

able parts, the inexperienced problem -solver may increase his difficulty. Subproblems interact. This observation is central to problem solving, particularly planning and design. When interactions can be anticipated, they can  guide the division of labor. When they are discovered late, the required changes can be difficult and expensive to incorporate. The difficulty of managing interactions is compounded by problem size and complexity. In large design projects, unforeseen interactions often consume a substantial share of the work of project managers [2]. This paper is concerned with ways to cope with and exploit interactions in design. Section 2 presents the constraint posting approach for managing interactions in design. Constraint posting has been implemented in a computer program (named MOLGEN) that has planned a few experiments in molecular genetics. In Section 3, the design of an experiment is used to illustrate the constraint posting ideas. In Section 4, the effectiveness of constraint posting on the sample problem is examined. The remaining sections trace the intellectual connections to other work on problem solving and propose suggestions for further research. This is the first of two papers about my thesis research on MOLGEN. Both papers are concerned with the use and organization of knowledge to make planning effective. This paper discusses the use of constraints to organize knowledge about subproblems in hierarchical planning. A companion paper [21] discusses the use of levels to organize control knowledge. It also develops a rationale for deciding when a planner should use heuristic reasoning. The research was carried out as part of the MOLGEN project at Stanford. A long term goal of this project is to build a knowledge-based program to assist geneticists in planning laboratory experiments. Towards that goal, two prototype planning systems have been constructed and used as vehicles for testing ideas about planning.

2. The Constraint Posting Approach to Design

The constraint posting approach depends on the view of systems as aggregates of loosely coupled subsystems. It models the design of such systems in terms of operations on constraints.

2.1. Nearly independent subproblems

In Sciences of the Artificial, Simon discussed the study and design of complex systems. He observed that when we study a complex system, whether it is natural or man-made, we often divide it into subsystems that can be studied separately without constant attention to their interactions. For example, in studying an automobile, we delineate subsystems such as the electrical system, fuel system, engine, and the brake system; in an animal, we delineate the nervous system, circulatory system, and the digestive system. Similarly, when we design complex systems, we tend to first map out the

design in terms of subsystems. Designers have advocated this top-down ap-PLANNING WITH CONSTRAINTS.