Article

PDDL+ planning with hybrid automata: foundations of translating must behavior

Authors:

Sergiy Bogomolov,

Daniele Magazzeni,

Stefano Minopoli,

Martin WehrleAuthors Info & Claims

ICAPS'15: Proceedings of the Twenty-Fifth International Conference on International Conference on Automated Planning and Scheduling

Pages 42 - 46

Published: 07 June 2015 Publication History

Publisher Site

Abstract

Planning in hybrid domains poses a special challenge due to the involved mixed discrete-continuous dynamics. A recent solving approach for such domains is based on applying model checking techniques on a translation of PDDL+ planning problems to hybrid automata. However, the proposed translation is limited because must behavior is only over-approximated, and hence, processes and events are not reflected exactly. In this paper, we present the theoretical foundation of an exact PDDL+ translation. We propose a schema to convert a hybrid automaton with must transitions into an equivalent hybrid automaton featuring only may transitions.

References

[1]

Alur, R.; Courcoubetis, C.; Halbwachs, N.; Henzinger, T.; Ho, P.; Nicolin, X.; Olivero, A.; Sifakis, J.; and Yovine, S. 1995. The algorithmic analysis of hybrid systems. Theoretical Computer Science 138:3-34.

Crossref

Google Scholar

[2]

Bogomolov, S.; Magazzeni, D.; Podelski, A.; and Wehrle, M. 2014. Planning as model checking in hybrid domains. In Proceedings of the Twenty Eighth Conference on Artificial Intelligence (AAAI-14). AAAI Press.

Crossref

Google Scholar

[3]

Bogomolov, S.; Magazzeni, D.; Minopoli, S.; and Wehrle, M. 2015. From PDDL+ to hybrid automata: Foundations of translating must behavior: Proof. Technical Report TR-2015-3, Verimag.

Google Scholar

[4]

Bryce, D., and Gao, S. 2015. SMT-based nonlinear PDDL+ planning. In Proceedings of the Twenty Nineth Conference on Artificial Intelligence (AAAI-15). AAAI Press.

Crossref

Google Scholar

[5]

Coles, A. J.; Coles, A.; Fox, M.; and Long, D. 2012. COLIN: Planning with continuous linear numeric change. Journal of Artificial Intelligence Research (JAIR) 44:1-96.

Crossref

Google Scholar

[6]

Della Penna, G.; Magazzeni, D.; Mercorio, F.; and Intrigila, B. 2009. UPMurphi: A tool for universal planning on PDDL+ problems. In Proceedings of the 19th International Conference on Automated Planning and Scheduling (ICAPS 2009). AAAI.

Google Scholar

[7]

Fox, M., and Long, D. 2006. Modelling mixed discrete-continuous domains for planning. Journal of Artificial Intelligence Research (JAIR) 27:235-297.

Crossref

Google Scholar

[8]

Li, H. X., and Williams, B. C. 2008. Generative planning for hybrid systems based on flow tubes. In ICAPS, 206-213.

Google Scholar

[9]

McDermott, D. V. 2003. Reasoning about autonomous processes in an estimated-regression planner. In ICAPS, 143-152.

Google Scholar

[10]

Penberthy, J. S., and Weld, D. S. 1994. Temporal planning with continuous change. In AAAI, 1010-1015.

Crossref

Google Scholar

[11]

Shin, J.-A., and Davis, E. 2005. Processes and continuous change in a sat-based planner. Artif. Intell. 166(1-2):194-253.

Crossref

Google Scholar

[12]

Wong-Toi, H. 1997. The synthesis of controllers for linear hybrid automata. In IEEE Conf. Decision and Control, 4607-4612. IEEE Computer Society.

Google Scholar

Cited By

View all

Fernández-González EWilliams BKarpas E(2019)ScottyActivityJournal of Artificial Intelligence Research10.1613/jair.1.1121962:1(579-664)Online publication date: 17-Apr-2019
https://dl.acm.org/doi/10.1613/jair.1.11219
Bogomolov SFrehse GGurung ALi DMartius GRay ROzay NPrabhakar P(2019)Falsification of hybrid systems using symbolic reachability and trajectory splicingProceedings of the 22nd ACM International Conference on Hybrid Systems: Computation and Control10.1145/3302504.3311813(1-10)Online publication date: 16-Apr-2019
https://dl.acm.org/doi/10.1145/3302504.3311813
Fernández-González EKarpas EWilliams BSingh SMarkovitch S(2017)Mixed discrete-continuous planning with convex optimizationProceedings of the Thirty-First AAAI Conference on Artificial Intelligence10.5555/3298023.3298232(4574-4580)Online publication date: 4-Feb-2017
https://dl.acm.org/doi/10.5555/3298023.3298232
Show More Cited By

PDDL+ planning with hybrid automata: foundations of translating must behavior
1. Theory of computation

Recommendations

Heuristic planning for PDDL+ domains
IJCAI'16: Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence

Planning with hybrid domains modelled in PDDL+ has been gaining research interest in the Automated Planning community in recent years. Hybrid domain models capture a more accurate representation of real world problems that involve continuous processes ...
Translation from Multisingular Hybrid Petri Nets to Multisingular Hybrid Automata

In this paper, we investigate some important aspects of a new formalism for modelling and verification of hybrid dynamic systems HDS, which is called multisingular hybrid Petri nets MSHPNs. This new hybrid formalism is aimed to bridge the gap between ...
SMT-based nonlinear PDDL+ planning
AAAI'15: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence

PDDL+ planning involves reasoning about mixed discrete-continuous change over time. Nearly all PDDL+ planners assume that continuous change is linear. We present a new technique that accommodates nonlinear change by encoding problems as nonlinear hybrid ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ICAPS'15: Proceedings of the Twenty-Fifth International Conference on International Conference on Automated Planning and Scheduling

June 2015

373 pages

ISBN:9781577357315

Publisher

AAAI Press

Publication History

Published: 07 June 2015

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 22 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Fernández-González EWilliams BKarpas E(2019)ScottyActivityJournal of Artificial Intelligence Research10.1613/jair.1.1121962:1(579-664)Online publication date: 17-Apr-2019
https://dl.acm.org/doi/10.1613/jair.1.11219
Bogomolov SFrehse GGurung ALi DMartius GRay ROzay NPrabhakar P(2019)Falsification of hybrid systems using symbolic reachability and trajectory splicingProceedings of the 22nd ACM International Conference on Hybrid Systems: Computation and Control10.1145/3302504.3311813(1-10)Online publication date: 16-Apr-2019
https://dl.acm.org/doi/10.1145/3302504.3311813
Fernández-González EKarpas EWilliams BSingh SMarkovitch S(2017)Mixed discrete-continuous planning with convex optimizationProceedings of the Thirty-First AAAI Conference on Artificial Intelligence10.5555/3298023.3298232(4574-4580)Online publication date: 4-Feb-2017
https://dl.acm.org/doi/10.5555/3298023.3298232
Piotrowski WFox MLong DMagazzeni DMercorio F(2016)Heuristic planning for PDDL+ domainsProceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence10.5555/3061053.3061071(3213-3219)Online publication date: 9-Jul-2016
https://dl.acm.org/doi/10.5555/3061053.3061071

Abstract

References

Cited By

Recommendations

Heuristic planning for PDDL+ domains

Translation from Multisingular Hybrid Petri Nets to Multisingular Hybrid Automata

SMT-based nonlinear PDDL+ planning

Comments

Information

Published In

Sponsors

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations