Maintaining Project Networks in Automated Artificial Intelligence Planning

AI automated plan synthesis programs ("planners") typically represent plans as a partially ordered network whose nodes are instants in time and whose arcs are precedence constraints. Such representations are essentially PERT charts. This paper provides an introduction to AI planners and illustrates the fact that many such PERT chart representations are created by a planner as it attempts to find a suitable plan. A planner's search must be guided if it is to produce suitable plans in realistic problem domains. One form of guidance is the imposition of constraints which must be satisfied by a valid plan. This paper concentrates on representing and reasoning about such constraints. Successful planning in some domains, e.g. job-shop scheduling, requires the recognition and satisfaction of constraints which prevent the simultaneous use of a shared resource by multiple agents. Such requirements can be expressed as disjunctive precedence constraints. In addition, the search for a valid plan is often structured so that rough plans are successively refined into plans with increased detail. In this refinement process, new constraints are often discovered. It should therefore be easy to add such new constraints. Finally, it is helpful to be able to express upper bound constraints on the elapsed time between two nodes in a PERT chart representation of a plan. Thus, this paper reports on knowledge representation and reasoning processes which facilitate: (1) disjunctive constraints, (2) the introduction of new constraints, and (3) upper bound constraints. A planner must backtrack when it is evident that further refinement of its current skeletal plan would be fruitless. Such an inconsistent state can be recognized when a plan's PERT chart representation contains an illegal cycle of positive overall length. When backtracking is required, dependency-directed backtracking is facilitated by recording "Nogood sets" of arcs whose simultaneous presence would result in such an illegal cycle. By using dependency-directed backtracking, chronological backtracking can be avoided.