×

Planning the project management way: Efficient planning by effective integration of causal and resource reasoning in RealPlan. (English) Zbl 1042.68104

Summary: In most real-world reasoning problems, planning and scheduling phases are loosely coupled. For example, in project planning, the user comes up with a task list and schedules it with a scheduling tool like Microsoft Project. One can view automated planning in a similar way in which there is an action selection phase where actions are selected and ordered to reach the desired goals, and a resource allocation phase where enough resources are assigned to ensure the successful execution of the chosen actions. On the other hand, most existing automated planners studied in Artificial Intelligence do not exploit this loose-coupling and perform both action selection and resource assignment employing the same algorithm. The current work shows that the above strategy severely curtails the scale-up potential of existing state of the art planners which can be overcome by leveraging the loose coupling.
Specifically, a novel planning framework called RealPlan is developed in which resource allocation is de-coupled from planning and is handled in a separate scheduling phase. The scheduling problem with discrete resources is represented as a constraint satisfaction problem problem, and the planner and scheduler interact either in a master-slave manner or in a peer-peer relationship. In the former, the scheduler simply tries to assign resources to the abstract causal plan passed to it by the planner and returns success. In the latter, a more sophisticated “multi-module dependency directed backtracking” approach is used where the failure explanation in the scheduler is translated back to the planner and serves as a nogood to direct planner search.
RealPlan not only preserves both the correctness as well as the quality (measured in length) of the plan but also improves efficiency. Moreover, the failure-driven learning of constraints can serve as an elegant and effective approach for integrating planning and scheduling systems. Beyond the context of planner efficiency, the current work can be viewed as an important step towards merging planning with real-world problem solving where plan failure during execution can be resolved by undertaking only necessary resource re-allocation and not complete re-planning.

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] (Allen, J.; Hendler, J.; Tate, A., Readings in Planning (1990), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA)
[2] Bacchus, F., AIPS-00 Planning Competition Results (2000), http://www.cs.toronto.edu/aips2000/SelfContainedAIPS-2000.ps
[3] Bäckström, C., Computational aspects of reordering plans, J. Artificial Intelligence Res., 9, 99-137 (1998) · Zbl 0903.68174
[4] Beck, J. C.; Fox, M. S., A generic framework for constraint-directed search and scheduling, AI Magazine, 19, 4, 101-130 (1998)
[5] Borning, A.; Marriott, K.; Stuckey, P.; Xiao, Y., Solving linear arithmetic constraints for user interface applications, (Proc. 1997 ACM Symposium on User Interface Software and Technology (1997))
[6] Blum, A.; Furst, M., Fast planning through planning graph analysis, (Proc. IJCAI-95, Montreal, Quebec (1995)), 1636-1642 · Zbl 0770.46035
[7] Cesta, A.; Cristiano, S., A time and resource problem in planning architectures, (Proc. ECP-96 (1996))
[8] Currie, K.; Tate, A., O-plan: The open planning architecture, Artificial Intelligence, 52, 49-86 (1991)
[9] Do, B.; Kambhampati, S., Solving planning graph by compiling it into CSP, (Proc. AIPS-00 (2000)) · Zbl 0983.68181
[10] El-Kholy, A.; Richards, B., Temporal and resource reasoning in planning: The parcPlan approach, (Proc. ECAI-96 (1996))
[11] Erol, K., Hierarchical task network planning: Formalization, analysis and implementation (1995), Ph.D. Dissertation, Dept. of Computer Science, Univ. Maryland: Ph.D. Dissertation, Dept. of Computer Science, Univ. Maryland College Park, MD
[12] Fikes, R.; Nilsson, N., STRIPS: A new approach to the application of theorem proving to problem solving, Artificial Intelligence, 2, 189-208 (1971) · Zbl 0234.68036
[13] Fink, E.; Yang, Q., Formalizing plan justifications, (Proc. CSCSI-92 (1992)), 9-14
[14] Fox, M. S., ISIS: A retrospective, (Zweben, M.; Fox, M. S., Intelligent Scheduling (1994), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 3-28
[15] Fox, M. S.; Long, D., The automatic inference of state invariants in TIM, J. Artificial Intelligence Res., 9, 367-421 (1999) · Zbl 0910.68199
[16] Fox, M. S.; Long, D., The detection and exploitation of symmetry in planning domains, (Proc. IJCAI-99, Stockholm, Sweden (1999))
[17] Hoffman, J.; Nebel, B., The FF planning system: Fast plan generation through heuristic search (2000), Submitted. Also website at http://www.informatik.uni-freiburg.de/ hoffmann/ff.html · Zbl 0970.68044
[18] Kambhampati, S., Planning graph as (dynamic) CSP: Exploiting EBL, DDB and other CSP techniques in Graphplan, J. Artificial Intelligence Res., 12, 1-34 (2000) · Zbl 0940.68100
[19] Kambhampati, S., On the relations between intelligent backtracking and failure-driven explanation-based learning in constraint satisfaction and planning, Artificial Intelligence, 105, 161-208 (1998) · Zbl 0909.68139
[20] Kambhampati, S., EBL and DDB for Graphplan, (Proc. IJCAI-99, Stockholm, Sweden (1999)) · Zbl 0940.68100
[21] Kambhampati, S.; Cutkoksy, M. R.; Tenenbaum, J. M.; Lee, S., Integrating general purpose planners and specialized reasoners: Case study of a hybrid planning architecture, IEEE Trans. Systems Man Cybernet. (Special issue on Planning, Scheduling and Control), 23, 6 (1993), An earlier version appears in Proc. AAAI-91)
[22] Kambhampati, S.; Parker, E.; Lambrecht, E., Understanding and extending Graphplan, (Proc. ECP (1997))
[23] Kambhampati, S.; Mali, A.; Srivastava, B., Hybrid planning for partially hierarchical domains, (Proc. AAAI-98, Madison, WI (1998))
[24] Kambhampati, S.; Srivastava, B., Universal classical planning: An algorithm for unifying state space and plan space planning approaches, (New Directions in AI Planning: EWSP-95 (1995), IOS Press: IOS Press Amsterdam)
[25] Kautz, H.; Selman, B., BLACKBOX A new approach to the application of theorem proving to problem solving, (Workshop Planning as Combinatorial Search, AIPS-98, Pittsburgh, PA (1998))
[26] Knoblock, C. A., Automatically generating abstractions for planning, Artificial Intelligence, 68, 2, 243-302 (1994) · Zbl 0942.68712
[27] Knoblock, C. A., Generating parallel execution plans with a partial-order planner, (Proc. AIPS (1994), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA)
[28] Koehler, J., Planning under resource constraints, (Proc. ECAI-98 (1998))
[29] Koehler, J.; Nebel, B.; Hoffmann, J.; Dimopoulos, Y., Extending planning graphs to an ADL subset, (Proc. ECP-97 (1997))
[30] Laborie, P.; Ghallab, M., Planning with sharable resource constraints, (Proc. IJCAI-95, Montreal, Quebec (1995))
[31] Liatsos, V.; Richards, B., Scaleability in planning, (Proc. ECP-99 (1999))
[32] McAllester, D.; Rosenblitt, D., Systematic nonlinear planning, (Proc. 9th NCAI-91 (1991)), 634-639
[33] McDermott, D., AIPS-98 planning competition results (1998), At ftp.cs.yale.edu/pub/mcdermott/aips comp-results.html
[34] McVey, C. B.; Atkins, E. M.; Durfee, E. H.; Shin, K. G., Development of iterative real-time scheduler to planner feedback, (Proc. IJCAI-97, Nagoya, Japan (1997))
[35] Moder, J. J.; Phillips, C. R., Project Management with CPM and PERT (1964), Reinhold Publ., Chapman & Hall Ltd: Reinhold Publ., Chapman & Hall Ltd London
[36] Microsoft Project Version 4.0 User Guide (1998), Microsoft Press
[37] Mittal, S.; Falkenhainer, B., Dynamic constraint satisfaction problems, (Proc. AAAI-90, Boston, MA (1990))
[38] Muscettola, N., Toward real-world science mission planning, (Proc. AAAI Fall Symposium (1994))
[39] Nebel, B.; Dimopoulos, Y.; Koehler, J., Ignoring irrelevant facts and operators in plan generation, (Proc. ECP-97 (1997))
[40] parcPlan home page (1999), http://www.icparc.ic.ac.uk/parcPlan/index.html
[41] Penberthy, J.; Weld, D., UCPOP: A sound, complete, partial order planner for ADL, (Proc. AAAI-94, Seattle, WA (1994)), 103-114
[42] Pinedo, M., Scheduling Theory, Algorithms and Systems (1995), Prentice Hall: Prentice Hall Englewood Cliffs, NJ · Zbl 1145.90393
[43] Prosser, P., Domain filtering can degrade intelligent backjumping search, (Proc. IJCAI-93, Chambéry, France (1993)), 262-267
[44] Sadeh, N., Micro-opportunistic Scheduling: The micro-boss factory scheduler (1994), Technical Report CMU-RI-TR-94-04, Carnegie Mellon Robotics Institute: Technical Report CMU-RI-TR-94-04, Carnegie Mellon Robotics Institute Pittsburgh, PA, Also in [57]
[45] Sadeh, N.; Hildum, D.; Laliberty, T.; McA’Nulty, J.; Kjenstad, D.; Tseng, A., A blackboard architecture for integrating process planning and production scheduling, Concurrent Engineering: Research and Applications, 6, 2 (1998)
[46] Smith, S., OPIS: A methodology and architecture for reactive scheduling, (Zweben, M.; Fox, M. S., Intelligent Scheduling (1994), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA)
[47] Smith, D. E.; Frank, J.; Jonsson, A. K., Bridging the gap between planning and scheduling, Knowledge Engineering Review (1999)
[48] Srivastava, B.; Kambhampati, S., Scaling up planning by teasing out resource scheduling, (Proc. ECP-99 (1999))
[49] Srivastava, B., Effective planning by efficient resource reasoning (2000), Ph.D. Dissertation, Arizona State Univ., AZ
[50] Srivastava, B., RealPlan: Decoupling of causal and resource reasoning in planning, (Proc. AAAI-00, Austin, TX (2000)) · Zbl 1042.68104
[51] van Beek, P.; Chen, X., CPlan: A constraint programming approach to planning, (Proc. AAAI-99, Orlando, FL (1999))
[52] Wilkins, D. E., Practical Planning: Extending the Classical AI Planning Paradigm (1988), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA
[53] Wolfman, S.; Weld, D., The LPSAT engine and its application to resource planning, (Proc. IJCAI-99, Stockholm, Sweden (1999))
[54] AltAlt web page (2000), http://rakaposhi.eas.asu.edu/altweb/altalt.html
[55] Yokoo, M.; Hirayama, K., Algorithms for distributed constraint satisfaction, A review, Autonomous Agents and Multi-Agent Systems, 3, 2, 185-207 (2000)
[56] Yokoo, M.; Hirayama, K., Distributed constraint satisfaction algorithm for complex local problems, (Proc. ICMAS-98 (1998))
[57] (Zweben, M.; Fox, M. S., Intelligent Scheduling (1994), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.