nach oben

Acta Informatica

Erschienen in:

01.10.2016 | Original Article

Planning and execution with flexible timelines: a formal account

verfasst von: Marta Cialdea Mayer, Andrea Orlandini, Alessandro Umbrico

Erschienen in: Acta Informatica | Ausgabe 6-8/2016

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Planning for real world problems with explicit temporal constraints is a challenging problem. Among several approaches, the use of flexible timelines in Planning and Scheduling has been shown to be successful in a number of concrete applications, such as, for instance, autonomous space systems. This paper builds on previous work and presents a revised and extended formal account of flexible timelines with the aim of providing a general semantics for related planning concepts such as domains, goals, problems, constraints, and flexible plans. Some sources of uncertainty are also modeled in the proposed framework and taken into account in the characterization of valid plans that are assumed not to take decisions on components the planner cannot control. A formal definition of different forms of plan controllability is also proposed.

Vorheriger Artikel Metric propositional neighborhood logic with an equivalence relation

Nächster Artikel Dynamic controllability via Timed Game Automata

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

In this work, “timeline” refers to what Cialdea Mayer et al. [16] call a flexible timeline, while non-flexible timelines are called “scheduled timelines”. The latter are defined as particular cases of (flexible) timelines.

For the same reason controllability tags are included in token descriptions.

Cialdea Mayer and Orlandini [15] do not allow constraints on the behavior of external state variables.

Abdedaim, Y., Asarin, E., Gallien, M., Ingrand, F., Lesire, C., Sighireanu, M.: Planning robust temporal plans: a comparison between CBTP and TGA approaches. In: Proceedings of the 17th International Conference on Automated Planning and Scheduling (ICAPS 2007), pp 2–10 (2007)

Allen, J.F.: Maintaining knowledge about temporal intervals. Commun. ACM 26(11), 832–843 (1983)CrossRefMATH

Barreiro, J., Boyce, M., Do, M., Frank, J., Iatauro, M., Kichkaylo, T., Morris, P., Ong, J., Remolina, E., Smith, T., Smith, D.: EUROPA: a platform for AI planning, scheduling, constraint programming, and optimization. In: The 4th International Competition on Knowledge Engineering for Planning and Scheduling (ICKEPS 2012) (2012)

Bensalem, S., Havelund, K., Orlandini, A.: Verification and validation meet planning and scheduling. Int. J. Softw. Tools Technol. Transfer 16(1), 1–12 (2014)CrossRef

Bernardini, S.: Constraint-based temporal planning: issues in domain modelling and search control. Ph.D. thesis, Università degli Studi di Trento (2008)

Castillo, L., Cortellessa, G., Yorke-Smith, N.: Special issue on scheduling and planning applications: selected papers from the SPARK workshop series. Comput. Intell. 27(1) (2011)

Cesta, A., Fratini, S.: The timeline representation framework as a planning and scheduling software development environment. In: Proceedings of the 27th Workshop of the UK Planning and Scheduling Special Interest Group (PlanSIG-08) (2008)

Cesta, A., Oddi, A.: DDL.1: A formal description of a constraint representation language for physical domains. In: Ghallab, M., Milani, A. (eds.) New directions in AI planning, pp. 341–352. IOS Press, Amsterdam (1996)

Cesta, A., Cortellessa, G., Fratini, S., Oddi, A., Policella, N.: An innovative product for space mission planning: an a posteriori evaluation. In: Proceedings of the Seventeenth International Conference on Automated Planning and Scheduling (ICAPS 2007), pp. 57–64 (2007)

10.

Cesta, A., Cortellessa, G., Fratini, S., Oddi, A.: Developing an end-to-end planning application from a timeline representation framework. In: Proceedings of the 21st Conference on Innovative Applications of Artificial Intelligence (IAAI-09), pp. 66–71 (2009)

11.

Cesta, A., Finzi, A., Fratini, S., Orlandini, A., Tronci, E.: Analyzing flexible timeline-based plans. In: Proceedings of the 19th European Conference on Artificial Intelligence (ECAI 2010), pp. 471–476 (2010)

12.

Cesta, A., Cortellessa, G., Fratini, S., Oddi, A.: MrSPOCK: steps in developing an end-to-end space application. Comput. Intell. 27(1), 83–102 (2011)MathSciNetCrossRef

13.

Chien, S., Tran, D., Rabideau, G., Schaffer, S., Mandl, D., Frye, S.: Timeline-based space operations scheduling with external constraints. In: Proceedings of the 20th International Conference on Automated Planning and Scheduling (ICAPS 2010), pp. 34–41 (2010)

14.

Chien, S.A., Johnston, M., Frank, J., Giuliano, M., Kavelaars, A., Lenzen, C., Policella, N.: A generalized timeline representation, services, and interface for automating space mission operations. In: Proceedings of Space Operations (SpaceOps) 2012 (2012)

15.

Cialdea Mayer, M., Orlandini, A.: An executable semantics of flexible plans in terms of Timed Game Automata. In: Proceedings of the 22nd International Symposium on Temporal Representation and Reasoning (TIME 2015), pp. 160–169 (2015)

16.

Cialdea Mayer, M., Orlandini, A., Umbrico, A.: A formal account of planning with flexible timelines. In: Proceedings of the 21st International Symposium on Temporal Representation and Reasoning (TIME 2014), pp. 37–46 (2014)

17.

Cimatti, A., Micheli, A., Roveri, M.: Timelines with temporal uncertainty. In: Proceedings of the 27th AAAI Conference on Artificial Intelligence, pp. 195–201 (2013)

18.

Finzi, A., Pirri, F.: Representing flexible temporal behaviors in the Situation Calculus. In: Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI-05), pp. 436–441 (2005)

19.

Frank, J.: What is a timeline? In: Proceedings of the 4th Workshop on Knowledge Engineering for Planning and Scheduling (KEPS 2013), pp. 31–38 (2013)

20.

Frank, J., Jónsson, A.: Constraint-based attribute and interval planning. Constraints 8(4), 339–364 (2003)MathSciNetCrossRefMATH

21.

Fratini, S., Pecora, F., Cesta, A.: Unifying planning and scheduling as timelines in a component-based perspective. Arch. Control Sci. 18(2), 231–271 (2008)MathSciNetMATH

22.

Hunsberger, L.: Fixing the semantics for dynamic controllability and providing a more practical characterization of dynamic execution strategies. In: Proceedings of the 16th International Symposium on Temporal Representation and Reasoning (TIME 2009), pp. 155–162 (2009)

23.

Hunsberger, L.: A fast incremental algorithm for managing the execution of dynamically controllable temporal networks. In: Proceedings of the 17th International Symposium on Temporal Representation and Reasoning (TIME 2010), pp. 121–128 (2010)

24.

Jonsson, A., Morris, P., Muscettola, N., Rajan, K., Smith, B.: Planning in interplanetary space: Theory and practice. In: Proceedings of the 5th International Conference on Artificial Intelligence Planning Systems (AIPS ’00), pp. 177–186 (2000)

25.

Laborie, P., Ghallab, M.: IxTeT: an integrated approach for plan generation and scheduling. In: Proceedings of the INRIA/IEEE Symposium on Emerging Technologies and Factory Automation (ETFA’95), pp. 485–495 (1995)

26.

Morris, P.: Dynamic controllability and dispatchability relationships. In: Integration of AI and OR Techniques in Constraint Programming, Proceedings of the 11th International Conference, CPAIOR 2014, Springer, LNCS, vol. 8451, pp. 464–479 (2014)

27.

Morris, P.H., Muscettola, N., Vidal, T.: Dynamic control of plans with temporal uncertainty. In: Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI 2001), pp. 494–502 (2001)

28.

Muscettola, N.: HSTS: Integrating planning and scheduling. In: Zweben, M., Fox, M.S. (eds.) Intelligent scheduling, pp. 169–212. Morgan Kauffmann, Burlington (1994)

29.

Orlandini, A., Finzi, A., Cesta, A., Fratini, S.: TGA-based controllers for flexible plan execution. In: KI 2011: Advances in Artificial Intelligence, Proceedings of the 34th Annual German Conference on AI, Springer, LNCS, vol. 7006, pp. 233–245 (2011)

30.

Orlandini, A., Suriano, M., Cesta, A., Finzi, A.: Controller synthesis for safety critical planning. In: Proceedings of the IEEE 25th International Conference on Tools with Artificial Intelligence (ICTAI 2013), pp. 306–313 (2013)

31.

Orlandini, A., Bernardi, G., Cesta, A., Finzi, A.: Planning meets verification and validation in a knowledge engineering environment. Intell. Artif. 8(1), 87–100 (2014)

32.

Simpson, R.M., Kitchin, D.E., McCluskey, T.L.: Planning domain definition using GIPO. Knowl. Eng. Rev. 22(2), 117–134 (2007)CrossRef

33.

Umbrico, A., Orlandini, A., Cialdea Mayer, M.: Enriching a temporal planner with resources and a hierarchy-based heuristic. In: AIxIA 2015 Advances in Artificial Intelligence, Proceedings of the 14th International Conference of the Italian Association for Artificial Intelligence, Springer, LNCS, vol. 9336, pp. 410–423 (2015)

34.

Vaquero, T.S., Silva, J.R., Tonidandel, F., Beck, J.C.: itSIMPLE: towards an integrated design system for real planning applications. Knowl. Eng. Rev. 28(2), 215–230 (2013)CrossRef

35.

Vidal, T., Fargier, H.: Handling contingency in temporal constraint networks: from consistency to controllabilities. J. Exp. Theor. Artif. Intell. 11, 23–45 (1999)CrossRefMATH

Titel: Planning and execution with flexible timelines: a formal account
verfasst von: Marta Cialdea Mayer
Andrea Orlandini
Alessandro Umbrico
Publikationsdatum: 01.10.2016
Verlag: Springer Berlin Heidelberg
Erschienen in: Acta Informatica / Ausgabe 6-8/2016
Print ISSN: 0001-5903
Elektronische ISSN: 1432-0525
DOI: https://doi.org/10.1007/s00236-015-0252-z

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 6-8/2016

Metric propositional neighborhood logic with an equivalence relation

Dynamic controllability via Timed Game Automata

Special issue: selected papers from the 21st international symposium on temporal representations and reasoning (TIME-2014)

Mining approximate interval-based temporal dependencies

Checking interval properties of computations

Efficient processing of simple temporal networks with uncertainty: algorithms for dynamic controllability verification

Premium Partner