Abstract
Many real world problems involve hybrid systems, subject to (continuous) physical effects and controlled by (discrete) digital equipments. Indeed, many efforts are being made to extend the current planning systems and modelling languages to support such kind of domains. However, hybrid systems often present also a nonlinear behaviour and planning with continuous nonlinear change that is still a challenging issue.
In this paper we present the UPMurphi tool, a universal planner based on the discretise and validate approach that is capable of reasoning with mixed discrete/continuous domains, fully respecting the semantics of PDDL+. Given an initial discretisation, the hybrid system is discretised and given as input to UPMurphi, which performs universal planning on such an approximated model and checks the correctness of the results. If the validation fails, the approach is repeated by appropriately refining the discretisation.
To show the effectiveness of our approach, the paper presents two real hybrid domains where universal planning has been successfully performed using the UPMurphi tool.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Aylett R, Soutter JK, Petley GJ, Chung PWH (1998) AI planning in a chemical plant domain. In: Prade H (ed) 13th European conference on artificial intelligence (ECAI), Brighton, UK, August 23–28. Wiley, New York, pp 622–626
Behrmann G, Cougnard A, David A, Fleury E, Larsen KG, Lime D (2007) UPPAAL-TIGA: Time for playing games! In: Damm W, Hermanns H (eds) 19th international conference on computer aided verification (CAV), July 3–7. Lecture notes in computer science, vol 4590. Springer, Berlin, pp 121–125
Bell KRW, Coles AJ, Coles AI, Fox M, Long D (2009) The role of AI planning as a decision support tool in power substation management. AI Commun 22(1):37–57
Bertoli P, Cimatti A, Pistore M, Roveri M, Traverso P (2001) MBP: a model based planner. In: Seventeenth international joint conference on artificial intelligence (IJCAI), workshop on planning under uncertainty and incomplete information (PRO-2). Seattle, Washington
Blake O, Bridges J, Chester E, Clemmet J, Hall S, Hannington M, Hurst S, Johnson G, Lewis S, Malin M, Morison I, Northey D, Pullan D, Rennie G, Richter L, Rothery D, Shaughnessy B, Sims M, Smith A, Townend M, Waugh L (2004) Beagle2 Mars: mission report. Lander Operations Control Centre, National Space Centre, University of Leicester. http://www2.le.ac.uk/departments/physics/research/src/downloads/B2-Report.zip/at_download/file
Blondel VD, Tsitsiklis JN (2000) A survey of computational complexity results in systems and control. Automatica 36(9):1249–1274
Boddy MS, Johnson DP (2002) A new method for the global solution of large systems of continuous constraints. In: Global optimization and constraint satisfaction, first international workshop global constraint optimization and constraint satisfaction (COCOS). Lecture Notes in Computer Science, vol 2861. Springer, Berlin, pp 142–156
Bonet B, Geffner H (2001) Planning and control in artificial intelligence: A unifying perspective. Appl Intell 14:237–252. doi:10.1023/A:1011286518035
Borrelli F (2003) Constrained optimal control for hybrid systems. In: Constrained optimal control of linear and hybrid systems. Lecture notes in control and information sciences, vol 290. Springer, Berlin, pp 143–171. doi:10.1007/3-540-36225-8_8
Brinksma E, Mader A (2000) Verification and optimization of a PLC control schedule. In: 7th international SPIN workshop. Lecture notes in computer science, vol 1885. Springer, Stanford, pp 73–92
Burch JR, Clarke EM, McMillan KL, Dill DL, Hwang LJ (1992) Symbolic model checking: 1020 states and beyond. Inf Comput 98(2):142–170
Cached Murphi Web Page (2006) http://www.dsi.uniroma1.it/~tronci/cached.murphi.html
Cimatti A, Roveri M, Traverso P (1998a) Strong planning in non-deterministic domains via model checking. In: Simmons Reid G, Manuela SS, Veloso M (eds) Fourth international conference on artificial intelligence planning systems (AIPS). AAAI Press, Pittsburgh, pp 36–43
Cimatti A, Pistore M, Roveri M, Traverso P (2003) Weak, strong, and strong cyclic planning via symbolic model checking. Artif Intell 147(1):35–84
Cimatti R, Roveri M, Traverso P (1998b) Automatic OBDD-based generation of universal plans in non-deterministic domains. In: Fifteenth national conference on artificial intelligence and tenth innovative applications of artificial intelligence conference (AAAI). AAAI Press / MIT Press, Madison, pp 875–881
Coles AI, Fox M, Long D, Smith AJ (2007) Planning with problems requiring temporal coordination. In: Twenty-second AAAI conference on artificial intelligence. AAAI Press, Vancouver, pp 415–420
Coles AJ, Coles AI, Fox M, Long D (2009) Temporal planning in domains with linear processes. In: Boutilier C (ed) 21st international joint conference on artificial intelligence (IJCAI), Pasadena, California, USA. pp 1671–1676
Della Penna G, Intrigila B, Melatti I, Tronci E, Venturini Zilli M (2004) Exploiting transition locality in automatic verification of finite state concurrent systems. Int J Softw Tools Technol Transf 6(4):320–341
Della Penna G, Intrigila B, Magazzeni D, Mercorio F (2009) Batch chemical plant PDDL+ model. http://www.di.univaq.it/gdellape/lamoka/go/?page=chemical
Deparade A (1999) A switched continuous model of VHS case study 1, draft. University of Dortmund. http://www-verimag.imag.fr/VHS/year1/cs11c.ps
Edelkamp S (2002) Mixed propositional and numeric planning in the model checking integrated planning system. In: Fox M, Coddington AM (eds) AIPS workshop on planning for temporal domains, Toulous, France, pp 47–55
Edelkamp S (2003) Taming numbers and durations in the model checking integrated planning system. J Artif Intell Res 20:195–238
Edelkamp S, Helmert M (2001) MIPS: The model-checking integrated planning system. AI Mag 22(3):67–72
Edelkamp S, Lafuente AL, Leue S (2001) Directed explicit model checking with HSF-SPIN. In: 8th international SPIN workshop on model checking of software. Springer, New York, pp 57–79
Edelkamp S, Jabbar S, Nazih M (2006) Large-scale optimal PDDL3 planning with MIPS-XXL. In: 5th international planning competition booklet. International conference on automated planning and scheduling, The English Lake District, Cumbria, UK, pp 28–31
Fourman M (2000) Propositional planning. In: Fifth international conference on artificial intelligence planning and scheduling—workshop on model theoretic approaches to planning (AIPS), Breckenridge, CO, USA, pp 10–17
Fox M, Long D (2002) PDDL+: modelling continuous time-dependent effects. In: 3rd international NASA workshop on planning and scheduling for space, Houston, Texas
Fox M, Long D (2003) PDDL2.1: An extension to PDDL for expressing temporal planning domains. J Artif Intell Res 20:61–124
Fox M, Long D (2006) Modelling mixed discrete-continuous domains for planning. J Artif Intell Res 27:235–297
Fox M, Howey R, Long D (2005) Validating plans in the context of processes and exogenous events. In: The twentieth national conference on artificial intelligence and the seventeenth innovative applications of artificial intelligence conference (AAAI/IAAI). AAAI Press / The MIT Press, Pittsburgh, pp 1151–1156
Gerevini A, Saetti A, Serina I (2004) Planning with numerical expressions in LPG. In: de Mántaras RL, Saitta L (eds) 16th European conference on artificial intelligence (ECAI). IOS Press, Valencia, pp 667–671
Giunchiglia F, Traverso P (2000) Planning as model checking. In: 5th European conference on planning: recent advances in AI planning. Springer, London, pp 1–20
Herrero J, Berlanga A, Molina J, Casar J (2005) Methods for operations planning in airport decision support systems. Appl Intell 22:183–206. doi:10.1007/s10791-005-6618-z
Holldobler S, Stor H (2000) Solving the entailment problem in the fluent calculus using binary decision diagrams. In: Chien S, Kambhampati S, Knoblock CA (eds) Fifth international conference on artificial intelligence planning systems (AIPS). AAAI Press, Breckenridge, pp 32–39
Howey R, Long D (2003) VAL’s progress: the automatic validation tool for PDDL2.1 used in the international planning competition. Strathprints: The University of Strathclyde Institutional Repository [http://eprintscdlrstrathacuk/perl/oai2] (United Kingdom)
Howey R, Long D, Fox M (2004a) VAL: Automatic plan validation, continuous effects and mixed initiative planning using PDDL. In: 16th IEEE international conference on tools with artificial intelligence (ICTAI). IEEE Computer Society, Boca Raton, pp 294–301
Howey R, Long D, Fox M (2004b) Validating plans with exogenous events. In: 23rd workshop of the UK planning and scheduling special interest group. University College Cork, Ireland, pp 78–87
Jensen R, Veloso M (1999) OBDD-based universal planning: Specifying and solving planning problems for synchronized agents in non-deterministic domains. Artifi Intell Today, Recent Trends Dev 1600:213–248
Kowalewski S (1998) Description of VHS case study 1: “Experimental Batch Plant”. http://astwww.chemietechnik.uni-dortmund.de/~vhs/cs1descr.zip
L’Aquila Model Checking Group (2010) UPMurphi web page. http://www.di.univaq.it/gdellape/lamoka/upmurphi
Léauté T, Williams BC (2005) Coordinating agile systems through the model-based execution of temporal plans. In: Veloso MM, Kambhampati S (eds) Twentieth national conference on artificial intelligence and the seventeenth innovative applications of artificial intelligence conference (AAAI/IAAI). AAAI Press / The MIT Press, Pittsburgh, pp 114–120
Li HX, Williams BC (2008) Generative planning for hybrid systems based on flow tubes. In: Rintanen J, Nebel B, Beck JC, Hansen EA (eds) Eighteenth international conference on automated planning and scheduling (ICAPS). AAAI Press, Sydney, pp 206–213
Martin M, Geffner H (2004) Learning generalized policies from planning examples using concept languages. Appl Intell 20(1):9–19
McDermott D (2000) The 1998 AI planning systems competition. AI Mag 21(2):33–55
McDermott D (2003) Reasoning about autonomous processes in an estimated regression planner. In: Giunchiglia E, Muscettola N, Nau DS (eds) Thirteenth international conference on automated planning and scheduling (ICAPS). AAAI Press, Trento, pp 143–152
McDermott D the AIPS1998 planning competition committee (1998). PDDL: the planning domain definition language. Tech. rep., available at: www.cs.yale.edu/homes/dvm
Molineaux M, Klenk M, Aha DW (2010) Planning in dynamic environments: Extending HTNs with nonlinear continuous effects. In: Fox M, Poole D (eds) Twenty-fourth AAAI conference on artificial intelligence (AAAI). AAAI Press, Atlanta, pp 1115–1120
Murphi Web Page (2004) http://sprout.stanford.edu/dill/murphi.html
Norris-Ip C, Dill DL (1993) Better verification through symmetry. In: Agnew D, Claesen LJM, Camposano R (eds) Computer hardware description languages and their applications, proceedings of the 11th IFIP WG10.2 international conference on computer hardware description languages and their applications—CHDL ’93, sponsored by IFIP WG10.2 and in cooperation with IEEE COMPSOC, Ottawa, Ontario, Canada, pp 97–111
Penberthy S, Weld D (1994) Temporal planning with continuous change. In: Twelfth national conference on artificial intelligence (AAAI). American Association for Artificial Intelligence, Menlo Park, pp 1010–1015
Reddy SY, Iatauro MJ, Kürklü E, Boyce ME, Frank JD, Jónsson AK (2008) Planning and monitoring solar array operations on the ISS. In: Eighteenth international conference on automated planning and scheduling (ICAPS), scheduling and planning applications workshop (SPARK), Sydney, Australia
Sapena O, Onaindía E (2008) Planning in highly dynamic environments: an anytime approach for planning under time constraints. Appl Intell 29:90–109. doi:10.1007/s10489-007-0083-x
Schmid U (2003) Inductive synthesis of functional programs: universal planning, folding of finite programs, and schema abstraction by analogical reasoning. Springer, New York
Schmid U, Wysotzki F (2000) Applying inductive program synthesis to macro learning. In: Chien S, Kambhampati S, Knoblock CA (eds) Fifth international conference on artificial intelligence planning systems (AIPS). AAAI Press, Breckenridge, pp 371–378
Schoppers M (1987) Universal plans of reactive robots in unpredictable environments. In: McDermott JP (ed) 10th international joint conference on artificial intelligence (IJCAI). Morgan Kaufmann, Milan, pp 1039–1046
Schuster HG (1988) Deterministic chaos: an introduction. Weinheim Physik
Shin JA, Davis E (2005) Processes and continuous change in a SAT-based planner. Artif Intell 166(1–2):194–253
Sontag E (1996) Interconnected automata and linear systems: a theoretical framework in discrete-time. In: Alur R, Henzinger T, Sontag E (eds) Hybrid systems III. Lecture notes in computer science, vol 1066. Springer, Berlin, pp 436–448
Stern U, Dill D (1995) Improved probabilistic verification by hash compaction. In: Camurati P, Eveking H (eds) Correct hardware design and verification methods. Lecture notes in computer science, vol 987. Springer, Berlin, pp 206–224
Wilson E, Karr C, Bennett J (2004) An adaptive, intelligent control system for slag foaming. Appl Intell 20:165–177. doi:10.1023/B:APIN.0000013338.39348.46
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Della Penna, G., Magazzeni, D. & Mercorio, F. A universal planning system for hybrid domains. Appl Intell 36, 932–959 (2012). https://doi.org/10.1007/s10489-011-0306-z
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10489-011-0306-z