Efficient Planning through Separate Resource Scheduling

Search Techniques for Problem Solving Under Uncertainty and Incomplete Information

Volume

Search Techniques for Problem Solving Under Uncertainty and Incomplete Information

Contents

Planning consists of selecting a course of actions to achieve the desired goals, and assigning enough resources to ensure successful execution of the chosen actions. Most planners do not distinguish these phases, and do both action selection and resource assignment using the same algorithm. We will show that this strategy severely curtails the scale-up potential of existing planners, including such recent ones as Graphplan and Satplan. Moreover, if some of the allocated resources become unavailable during plan execution, re-planning is needed. In response, we propose a novel planning framework in which resource allocation is teased apart from planning, and is handled in a separate ``scheduling'' phase. We disregard resources during planning and this expedites the detection of inherently unsolvable problems. Moreover, if there are enough resources to overcome any resource conflict in the plan, scheduling is trivial and independent of the actual resource level. We categorize the remaining spectrum of problems based on how efficiently the scheduling can be done. We implement a prototype of our approach on top of the Graphplan algorithm and present promising results. Another benefit of our approach is that if a plan fails during execution, only necessary resource re-allocation is needed and not complete re-planning.