×

zbMATH — the first resource for mathematics

CASP solutions for planning in hybrid domains. (English) Zbl 1379.68039
Summary: Constraint answer set programming (CASP) is an extension of answer set programming that allows for numerical constraints to be added in the rules. PDDL+ is an extension of the PDDL standard language of automated planning for modeling mixed discrete-continuous dynamics. In this paper, we present CASP solutions for dealing with PDDL+ problems, i.e., encoding from PDDL+ to CASP, and extensions to the algorithm of the ezcsp CASP solver in order to solve CASP programs arising from PDDL+ domains. An experimental analysis, performed on well-known linear and non-linear variants of PDDL+ domains, involving various configurations of the ezcsp solver, other CASP solvers, and PDDL+ planners, shows the viability of our solution.

MSC:
68N17 Logic programming
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Software:
Clingcon; COLIN
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bae, K.; Ölveczky, P. C.; Kong, S.; Gao, S.; Clarke, E. M.; Abate, A.; Fainekos, G. E., (2016)
[2] Balduccini, M., (2009)
[3] Balduccini, M.; Gelfond, M.; Doherty, P.; Mccarthy, J.; Williams, M.-A., (2003)
[4] Balduccini, M.; Gelfond, M.; Nogueira, M., Answer set based design of knowledge systems, Annals of Mathematics and Artificial Intelligence, 47, 1-2, 183-219, (2006) · Zbl 1105.68105
[5] Balduccini, M.; Lierler, Y., Integration schemas for constraint answer set programming: A case study, Theory and Practice of Logic Programming, 13, 4-5, (2013)
[6] Baral, C., Knowledge Representation, Reasoning, and Declarative Problem Solving, (2003), Cambridge University Press · Zbl 1056.68139
[7] Baral, C.; Son, T. C.; Tuan, L.; Fensel, D.; Giunchiglia, F.; Mcguinness, D. L.; Williams, M., (2002)
[8] Baselice, S.; Bonatti, P. A.; Gelfond, M.; Gabbrielli, M.; Gupta, G., (2005)
[9] Bogomolov, S.; Magazzeni, D.; Minopoli, S.; Wehrle, M.; Brafman, R. I.; Domshlak, C.; Haslum, P.; Zilberstein, S., (2015)
[10] Bogomolov, S.; Magazzeni, D.; Podelski, A.; Wehrle, M.; Brodley, C. E.; Stone, P., (2014)
[11] Bryce, D.; Gao, S.; Musliner, D. J.; Goldman, R. P.; Bonet, B.; Koenig, S., (2015)
[12] Cashmore, M.; Fox, M.; Long, D.; Magazzeni, D.; Coles, A. J.; Coles, A.; Edelkamp, S.; Magazzeni, D.; Sanner, S., (2016)
[13] Cavada, R.; Cimatti, A.; Dorigatti, M.; Griggio, A.; Mariotti, A.; Micheli, A.; Mover, S.; Roveri, M.; Tonetta, S.; Biere, A.; Bloem, R., (2014)
[14] Cervesato, I.; Montanari, A., (2000)
[15] Chintabathina, S., (2013)
[16] Chintabathina, S.; Gelfond, M.; Watson, R., (2005)
[17] Cimatti, A.; Giunchiglia, E.; Giunchiglia, F.; Traverso, P., Recent Advances in AI Planning, Planning via model checking: A decision procedure for AR, 130-142, (1997), Springer
[18] Cimatti, A.; Griggio, A.; Mover, S.; Tonetta, S., (2015)
[19] Coles, A. J.; Coles, A.; Fox, M.; Long, D., COLIN: Planning with continuous linear numeric change, Journal of Artificial Intelligence Research, 44, 1-96, (2012) · Zbl 1280.68236
[20] Della Penna, G.; Intrigila, B.; Magazzeni, D.; Mercorio, F.; Brafman, R. I.; Geffner, H.; Hoffmann, J.; Kautz, H. A., (2010)
[21] Della Penna, G.; Magazzeni, D.; Mercorio, F., A universal planning system for hybrid domains, Applied Intelligence, 36, 4, 932-959, (2012)
[22] Della Penna, G.; Magazzeni, D.; Mercorio, F.; Intrigila, B.; Gerevini, A.; Howe, A. E.; Cesta, A.; Refanidis, I., (2009)
[23] Evans, C., (1990)
[24] Fox, M.; Long, D., Modelling mixed discrete-continuous domains for planning, Journal of Artificial Intelligence Research, 27, 235-297, (2006) · Zbl 1182.68238
[25] Fox, M.; Long, D.; Magazzeni, D.; Bacchus, F.; Domshlak, C.; Edelkamp, S.; Helmert, M., (2011)
[26] Fox, M.; Long, D.; Magazzeni, D., Plan-based policies for efficient multiple battery load management, Journal of Artificial Intelligence Research, 44, 335-382, (2012) · Zbl 1253.68299
[27] Gelfond, M.; Lifschitz, V.; Kowalski, R. A.; Bowen, K. A., (1988)
[28] Gelfond, M.; Lifschitz, V., Classical negation in logic programs and disjunctive databases, New Generation Computing, 9, 365-385, (1991) · Zbl 0735.68012
[29] Gelfond, M.; Lifschitz, V., Representing action and change by logic programs, Journal of Logic Programming, 17, 2-4, 301-321, (1993) · Zbl 0783.68024
[30] Henzinger, T. A., (1996)
[31] Henzinger, T. A.; Otop, J.; Fränzle, M.; Lygeros, J., (2014)
[32] Howey, R.; Long, D.; Fox, M., (2004)
[33] Jaffar, J.; Lassez, J.-L., (1987)
[34] Karaman, S.; Walter, M. R.; Perez, A.; Frazzoli, E.; Teller, S. J., (2011)
[35] Katriel, I.; Van Hoeve, W.-J.; Rossi, F.; Van Beek, P.; Walsh, T., Handbook of Constraint Programming, Global constraints, 169-208, (2006), Elsevier
[36] Kautz, H. A.; Selman, B.; Neumann, B., (1992)
[37] Lahijanian, M.; Kavraki, L. E.; Vardi, M. Y., (2014)
[38] Li, H. X.; Williams, B. C.; Rintanen, J.; Nebel, B.; Beck, J. C.; Hansen, E. A., (2008)
[39] Lierler, Y., Relating constraint answer set programming languages and algorithms, Artificial Intelligence, 207, 1-22, (2014) · Zbl 1334.68041
[40] Lifschitz, V., Answer set programming and plan generation, Artificial Intelligence, 138, 39-54, (2002) · Zbl 0995.68020
[41] Liu, J.; Ozay, N.; Fränzle, M.; Lygeros, J., (2014)
[42] Maly, M. R.; Lahijanian, M.; Kavraki, L. E.; Kress-Gazit, H.; Vardi, M. Y.; Belta, C.; Ivancic, F., (2013)
[43] Marek, V. W.; Truszczynski, M., The Logic Programming Paradigm: A 25-Year Perspective, Stable models and an alternative logic programming paradigm, 375-398, (1999), Springer Verlag: Springer Verlag, Berlin · Zbl 0979.68524
[44] Marriott, K.; Stuckey, P. J.; Wallace, M., Handbook of Constraint Programming, 409-452, (2006), Elsevier
[45] Mcdermott, D. V.; Giunchiglia, E.; Muscettola, N.; Nau, D. S., (2003)
[46] Mellarkod, V. S.; Gelfond, M.; Zhang, Y., Integrating answer set programming and constraint logic programming, Annals of Mathematics and Artificial Intelligence, 53, 1, 251-287, (2008) · Zbl 1165.68504
[47] Miller, R.; Shanahan, M.; Aiello, L. C.; Doyle, J.; Shapiro, S. C., (1996)
[48] Nau, D.; Ghallab, M.; Traverso, P., Automated Planning: Theory & Practice, (2004), Morgan Kaufmann
[49] Niemelä, I., Logic programs with stable model semantics as a constraint programming paradigm, Annals of Mathematics and Artificial Intelligence, 25, 3-4, 241, (1999) · Zbl 0940.68018
[50] Ostrowski, M.; Schaub, T., ASP modulo CSP: The clingcon system, Theory and Practice of Logic Programming, 12, 4-5, 485-503, (2012) · Zbl 1260.68066
[51] Penberthy, J. S.; Weld, D. S.; Hayes-Roth, B.; Korf, R. E., (1994)
[52] Piacentini, C.; Magazzeni, D.; Long, D.; Fox, M.; Dent, C.; Coles, A. J.; Coles, A.; Edelkamp, S.; Magazzeni, D.; Sanner, S., (2016)
[53] Piotrowski, W.; Fox, M.; Long, D.; Magazzeni, D.; Mercorio, F.; Kambhampati, S., (2016)
[54] Plaku, E.; Kavraki, L. E.; Vardi, M. Y., Falsification of LTL safety properties in hybrid systems, Software and Tools for Technology Transfer, 15, 4, 305-320, (2013) · Zbl 1234.68264
[55] Reiter, R., Knowledge in Action: Logical Foundations for Specifying and Implementing Dynamical Systems, (2001), MIT Press · Zbl 1018.03022
[56] Shanahan, M., (1990)
[57] Shin, J.-A.; Davis, E., Processes and continuous change in a SAT-based planner, Artificial Intelligence, 166, 1-2, 194-253, (2005) · Zbl 1132.68711
[58] Smith, B. M.; Rossi, F.; Van Beek, P.; Walsh, T., Handbook of Constraint Programming, Modelling, 377-406, (2006), Elsevier
[59] Tabuada, P.; Pappas, G. J.; Lima, P. U.; Tomlin, C.; Greenstreet, M. R., (2002)
[60] Vallati, M.; Magazzeni, D.; Schutter, B. D.; Chrpa, L.; Mccluskey, T. L.; Schuurmans, D.; Wellman, M. P., (2016)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.