This study proposes a novel temporal planning approach based on Hierarchical Task Network (HTN) with uncontrollable durations for emergency decision-making. The objective is to generate a dynamically controllable (DC) plan which takes into account uncontrollable durations beforehand and to execute the plan via scheduling the actions dynamically. In this study, the action durations are modelled as temporal intervals by Simple Temporal Network with Uncertainty (STNU). Firstly, the temporal constraints among tasks are represented and reasoned. Next, a mechanism is proposed to hierarchically inherit the temporal constraints in HTN planning. Furthermore, two works are explored to generate a DC plan more efficiently. The one is to construct a temporal network of tasks and check its dynamic controllability. The other one is to put forward two rules to boost the DC checking in planning. An empirical study on flood emergency response is conducted to evaluate the planning approach. The experimental results demonstrate the effectiveness and efficiency of the planning approach for emergency decision-making.
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.
2.
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.
3.
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.
4.
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.
5.
CurrieK. and TateA., O-Plan: The open planning architecture, Artificial Intelligence52(1) (1991), 49–86.
6.
NtuenC.A., BalogunO., BoyleE. and TurnerA., Supporting command and control training functions in the emergency management domain using cognitive systems engineering, Ergonomics49(12-13) (2006), 1415–1436.
7.
SmirnovA., PashkinM., ChilovN. and LevashovaT., Context-based disaster management support, Proceedings of the IEEE Workshop on Distributed Intelligent Systems: Collective Intelligence and Its Applications (DIS’ 06), Prague, Czech Republic, 2006, pp. 291–296.
8.
TuroffM., ChumerM., Van de WalleB. and YaoX., The design of a dynamic emergency response management information system, Journal of Information Technology Theory and Application5(4) (2004), 1–36.
9.
VidalT. and FargierH., Handling contingency in temporal constraint networks: From consistency to controllabilities, Journal of Experimental & Theoretical Artificial Intelligence11(1) (1999), 23–45.
10.
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.
11.
TangP. and ShenG.Q., Decision-making model to generate novel emergency response plans for improving coordination during large-scale emergencies, Knowledge-Based Systems90 (2015), 111–128.
12.
Mausam and WeldD.S., Planning with durative actions in stochastic domains, Journal of Artificial Intelligence Research31(1) (2008), 33–82.
13.
BeaudryE., KabanzaF. and MichaudF., Planning for Concurrent Action Executions Under Action Duration Uncertainty Using Dynamically Generated Bayesian Networks, Proceedings of the 20th International Conference on Automated Planning and Scheduling, Toronto, Ontario, CA, 2010, pp 10–17.
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, Hungary1996, pp. 48–54.
15.
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.
16.
CimattiA., MicheliA. and RoveriM., Strong temporal planning with uncontrollable durations: A state-space approach, Proceedings of the 29th AAAI Conference on Artificial Intelligence, Austin, Texas, USA, 2015, pp. 3254–3260.
17.
ColesA., ColesA., FoxM., LongD., COLIN: lanning with continuous linear numeric change, Journal of Artificial Intelligence Research44 (2012), 1–96.
18.
MicheliA., DoM. and SmithD.E., Compiling Away Uncertainty in Strong Temporal Planning with Uncontrollable Durations, Proceedings of the 24th International Joint Conference on Artificial Intelligence, Buenos Aires, Argentina, 2015, pp. 1631–1637.
19.
CimattiA., MicheliA. and RoveriM., Timelines with Temporal Uncertainty, Proceedings of the 27th AAAI Conference on Artificial Intelligence, Bellevue, Washington, USA, (2013), 195–202.
20.
BartákR., MorrisR.A. and VenableK.B., An Introduction to Constraint-Based Temporal Reasoning, Morgan & Claypool Publishers, 2014.
21.
WilkinsD.E., Can AI planners solve practical problems?Computational intelligence6(4) (1990), 232–246.
22.
WilkinsD.E., Practical planning: Extending the classical AI planning paradigm, Morgan Kaufmann, 2014.
23.
TateA., DrabbleB. and KirbyR., O-Plan2: An open architecture for command, planning and control, In Intelligent Scheduling, Morgan Kaufmann, 1994, pp. 213–239.
24.
NauD., AuT.C., IlghamiO., KuterU., MurdockJ.W., WuD. and YamanF., SHOP2: An HTN planning system, Journal of Artificial Intelligence Research20 (2003), 379–404.
25.
Yorke-SmithN., Exploiting the Structure of Hierarchical Plans in Temporal Constraint Propagation, Proceedings of the 20th National Conference on Artificial Intelligence, Pittsburgh, Pennsylvania, USA, 2005, pp. 1223–1228.
CastilloL., Fernández-OlivaresJ., Garcia-PerezO. and PalaoF., Efficiently Handling Temporal Knowledge in an HTN Planner, Proceedings of the 17th International Conference on Automated Planning and Scheduling, Cumbria, UK, 2006, pp. 63–72.
28.
GoldmanR.P., Durative Planning in HTNs, Proceedings of the 17th International Conference on Automated Planning and Scheduling, Cumbria, UK, 2006, pp. 382–385.
29.
YamanF., BenyoB. and MulvehillA.M., Temporal Milestones in HTNs, Proceedings of the 27th AAAI Conference on Artificial Intelligence, Bellevue, Washington, USA, 2013.
30.
BiundoS., HolzerR. and SchattenbergB., Project planning under temporal uncertainty, In Planning, Scheduling, and Constraint Satisfaction: From Theory to Practice, IOS Press, 2004, pp. 189–198.
31.
GeorgievskiI. and AielloM., HTN planning: Overview, comparison, and beyond, Artificial Intelligence222 (2015), 124–156.
32.
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.
33.
WilkinsD.E., MyersK.L., LowranceJ.D. and WesleyL.P., Planning and reacting in uncertain and dynamic environments, Journal of Experimental & Theoretical Artificial Intelligence7(1) (1995), 121–152.
34.
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.
35.
GhallabM., NauD., TraversoP., Automated planning: Theory & practice, Elsevier, 2004.
36.
EstlinT.A., ChienS.A. and WangX., Hierarchical task network and operator-based planning: Two complementary approaches to real-world planning, Journal of Experimental & Theoretical Artificial Intelligence13(4) (2001), 379–395.
37.
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.
38.
NilssonM., KvarnströmJ. and DohertyP., Efficient processing of simple temporal networks with uncertainty: Algorithms for dynamic controllability verification, Acta Informatica (2015), 1–30.
39.
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.
40.
HunsbergerL., Efficient execution of dynamically controllable simple temporal networks with uncertainty, Acta Informatica (2015), 1–59.
