Maintaining Project Networks in Automated Artificial Intelligence Planning

Colin E. Bell
Additional contact information
Colin E. Bell: Department of Management Sciences, University of Iowa, Iowa City, Iowa 52242

Management Science, 1989, vol. 35, issue 10, 1192-1214

Abstract: 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.

Keywords: artificial intelligence; project planning; disjunctive constraints; temporal logic (search for similar items in EconPapers)
Date: 1989
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.35.10.1192 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:35:y:1989:i:10:p:1192-1214

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().