Emergency decision-making confronts a problem where emergency tasks coordinating to achieve emergency objectives are subject to urgent time and limited resources. Actions with uncontrollable durations make the problem more complicated. This paper proposes a novel resource-constrained Hierarchical Task Network planning approach under uncontrollable durations for emergency decision-making. The objective is to generate a dynamically controllable plan with constrained resources and execute the plan via scheduling actions dynamically. Two of the most general categories of resources in emergency decision-making, consumable resources and reusable resources, are considered. First, timed initial literals are extended to present timed resources and the constraints of timed literals are transformed to impose restrictions on actions in planning. Second, a mechanism is explored to hierarchically inherit the resource constraints of compound tasks by subtasks during Hierarchical Task Network planning. Third, two categories of resource constraints are checked, respectively. Potential resource conflicts are resolved via adding precedence constraints. Finally, experimental studies are conducted to evaluate the planning approach. The results demonstrate the effectiveness and efficiency of the planning approach for emergency decision-making.
SmithD.E., FrankJ. and JónssonA.K., Bridging the gap between planning and scheduling, The Knowledge Engineering Review15(01) (2000), 47–83.
2.
ErolK., HendlerJ. and NauD., HTN Planning: Complexity and Expressivity, Proceedings of the 12th National Conference on Artificial Intelligence, Seattle, Washington, USA, 1994, pp. 1123–1128.
3.
ErolK., HendlerJ. and NauD., UMCP: A Sound and Complete Procedure for Hierarchical Task Network Planning, Proceedings of the 2nd International Conference on Artificial Intelligence Planning Systems, Chicago, Illinois, USA, 1994, pp. 249–254.
4.
AsunciónM.D.L., CastilloL., Fdez-OlivaresJ., García-PérezÓ., GonzálezA. and PalaoF., SIADEX: An Interactive Knowledge-Based Planner for Decision Support in Forest Fire Fighting, AI Communications18(4) (2005), 257–268.
5.
BiundoS. and SchattenbergB., From Abstract Crisis to Concrete Relief: A Preliminary Report on Combining State Abstraction and HTN Planning, Proceedings of the 6th European Conference on Planning, Toledo, Spain, 2001, pp. 157–168.
6.
HayashiH., TokuraS., OzakiF. and HasegawaT., Emergency HTN Planning, In Intelligent Automation and Computer Engineering, Springer, 2010, pp. 27–40.
7.
LiuD., WangH., QiC., ZhaoP. and WangJ., Hierarchical task network-based emergency task planning with incomplete information, concurrency and uncertain duration, Knowledge-Based Systems112 (2016), 67–79.
8.
ZhaoP., WangH., QiC. and LiuD., HTN planning with uncontrollable durations for emergency decision-making, Journal of Intelligent & Fuzzy Systems33(1) (2017), 255–267.
9.
WilkinsD.E., Can AI planners solve practical problems?Computational Intelligence6(4) (1990), 232–246.
10.
CurrieK. and TateA., O-Plan: The open planning architecture, Artificial Intelligence52(1) (1991), 49–86.
11.
WangZ., WangH., QiC. and WangJ., A resource enhanced HTN planning approach for emergency decision-making, Applied Intelligence38(2) (2013), 226–238.
12.
VidalT. and FargierH., Handling contingency in temporal constraint networks: From consistency to controllabilities, Journal of Experimental & Theoretical Artificial Intelligence11(1) (1999), 23–45.
13.
MorrisP., MuscettolaN. and VidalT., Dynamic Control of Plans with Temporal Uncertainty, Proceedings of the 17th International Joint Conference on Artificial Intelligence, Seattle, Washington, USA, 2001, pp. 494–502.
14.
VidalT. and GhallabM., Dealing with Uncertain Durations In Temporal Constraint Networks dedicated to Planning, Proceedings of the 12th European Conference on Artificial Intelligence, Budapest, Hungary, 1996, pp. 48–54
.
15.
BartákR., MorrisR.A. and VenableK.B., An Introduction to Constraint-Based Temporal Reasoning, Morgan & Claypool Publishers, 2014.
16.
WilkinsD.E., Practical planning: Extending the classical AI planning paradigm, Morgan Kaufmann, 2014.
17.
TateA., DrabbleB. and KirbyR., O-Plan2: An open architecture for command, planning and control, In Intelligent Scheduling, Morgan Kaufmann, 1994, pp. 213–239.
18.
DvorakF., BartakR., Bit-MonnotA., IngrandF. and GhallabM., Planning and Acting with Temporal and Hierarchical Decomposition Models, Proceedings of the 26th International Conference on Tools with Artificial Intelligence, Limassol, Cyprus, 2014, pp. 115–121.
19.
QiC., WangD., Muñoz-AvilaH., ZhaoP. and WangH., Hierarchical task network planning with resources and temporal constraints, Knowledge-Based Systems113 (2017), 17–32.
20.
LaboneP. and GhallabM., Planning with Sharable Resource Constraints, Proceedings of the 14th International Joint Conference on Artificial Intelligence, Montreal, Canada, 1995, pp. 1643–1649.
21.
El-KholyA. and RichardsB., Temporal and Resource Reasoning in Planning: The ParcPLAN Approach, Proceedings of the 12th European Conference on Artificial Intelligence, Budapest, Hungary, 1996, pp. 614–618.
22.
CestaA. and StellaC., A Time and Resource Problem for Planning Architectures, Proceedings of the 4th European Conference on Planning: Recent Advances in AI Planning, Toulouse, France, 1997, pp. 117–129.
23.
DvořákF. and BartákR., Integrating Time and Resources into Planning, Proceedings of the 22nd IEEE International Conference on Tools with Artificial Intelligence, Arras, France, 2010, pp. 71–78.
24.
KvarnströmJ., DohertyP. and HaslumP., Extending TAL Planner with Concurrency and Resources, Proceedings of the 14th European Conference on Artificial Intelligence, Berlin, Germany, 2000, pp. 501–505.
25.
KvarnströmJ. and DohertyP., TAL Planner: A temporal logic based forward chaining planner, Annals of Mathematics and Artificial Intelligence30(1-4) (2000), 119–169.
26.
MorrisP. and MuscettolaN., Temporal Dynamic Controllability Revisited, Proceedings of the 20th National Conference on Artificial Intelligence, Pittsburgh, Pennsylvania, USA, 2005, pp. 1193–1198.
27.
MorrisP., A Structural Characterization of Temporal Dynamic Controllability, In Principles and Practice of Constraint Programming-CP 2006, Springer, 2006, pp. 375–389.
28.
MorrisP., Dynamic Controllability and Dispatchability Relationships, In Integration of AI and OR Techniques in Constraint Programming, Springer, 2014, pp. 464–479.
29.
ShahJ., StedlJ., WilliamsB. and RobertsonP., A Fast Incremental Algorithm for Maintaining Dispatchability of Partially Controllable Plans, Proceedings of the 17th International Conference on Automated Planning and Scheduling, Providence, Rhode Island, USA, 2007, pp. 296–303.
30.
StedlJ. and WilliamsB., A Fast Incremental Dynamic Controllability Algorithm, Proceedings of the International Conference on Planning and Scheduling Workshop on Plan Execution: A Reality Check, Monterey, California, USA, 2005, pp. 69–75.
31.
NilssonM., KvarnströmJ. and DohertyP., Efficientidc: A Faster Incremental Dynamic Controllability Algorithm, Proceedings of the 24th International Conference on Automated Planning and Scheduling, Portsmouth, New Hampshire, USA, 2014.
32.
NilssonM., KvarnströmJ. and DohertyP., Incremental Dynamic Controllability in Cubic Worst-Case Time, Proceedings of the 21st International Symposium on Temporal Representation and Reasoning, Verona, Italy, 2014, pp. 17–26.
33.
NauD., AuT.-C., IlghamiO., KuterU., MurdockJ.W., WuD. and YamanF., SHOP2: An HTN planning system, Journal of Artificial Intelligence Research20 (2003), 379–404.
34.
EdelkampS. and HoffmannJ., PDDL2.2: The language for the classical part of the 4th international planning competition (Technical Report 195), (Albert-Ludwigs-Universitat Freiburg, Institut fur Informatik, 2004.
35.
GereviniA.E., HaslumP., LongD., SaettiA. and DimopoulosY., Deterministic planning in the fifth international planning competition: PDDL3 and experimental evaluation of the planners, Artificial Intelligence173(5–6) (2009), 619–668.
36.
GeorgievskiI. and AielloM., HTN planning: Overview, comparison, and beyond, Artificial Intelligence222 (2015), 124–156.
37.
GarridoA. and BarberF., Integrating planning and scheduling, Applied Artificial Intelligence15(5) (2001), 471–491.
38.
MorrisP. and MuscettolaN., Execution of Temporal Plans with Uncertainty, Proceedings of the 17th National Conference on Artificial Intelligence, Austin, Texas, USA, 2000, pp. 491–496.
39.
NilssonM., KvarnströmJ. and DohertyP., Efficient processing of simple temporal networks with uncertainty: Algorithms for dynamic controllability verification, Acta Informatica (2015), 1–30.
40.
Bedrax-WeissT., McGannC. and RamakrishnanS., Formalizing Resources for Planning, Proceedings of the 13th International Conference on Automated Planning and Scheduling Workshop on PDDL, Trento, Italy, 2003, pp. 7–14.
41.
GhallabM., NauD., TraversoP., Automated planning: Theory & practice, Elsevier, 2004.
42.
LaborieP., Algorithms for Propagating Resource Constraints in AI Planning and Scheduling: Existing Approaches and New Results, Proceedings of the 6th European Conference on Planning, Toledo, Spain, 2001.
43.
LaborieP., Algorithms for propagating resource constraints in AI planning and scheduling: Existing approaches and new results, Artificial Intelligence143 (2003), 151–188.
44.
LongD., FoxM., SebastiaL. and CoddingtonA., An Examination of Resources in Planning, Proceedings of the 19th Workshop of the UK Planning & Scheduling Special Interest Group, Milton Keynes, England, UK, 2000.
45.
NakhostH., HoffmannJ. and MüllerM., Resource-Constrained Planning: A Monte Carlo Random Walk Approach, Proceedings of the 22nd International Conference on Automated Planning and Scheduling, Atibaia, Sao Paulo; Brazil, 2012, pp. 181–189.
46.
HoffmannJ. and EdelkampS., The deterministic part of IPC-4: An overview, Journal of Artificial Intelligence Research24(1) (2005), 519–579.
