×

zbMATH — the first resource for mathematics

Agent planning programs. (English) Zbl 1344.68245
Summary: This work proposes a novel high-level paradigm, agent planning programs, for modeling agents behavior, which suitably mixes automated planning with agent-oriented programming. Agent planning programs are finite-state programs, possibly containing loops, whose atomic instructions consist of a guard, a maintenance goal, and an achievement goal, which act as precondition-invariance-postcondition assertions in program specification. Such programs are to be executed in possibly nondeterministic planning domains and their execution requires generating plans that meet the goals specified in the atomic instructions, while respecting the program control flow. In this paper, we define the problem of automatically synthesizing the required plans to execute an agent planning program, propose a solution technique based on model checking of two-player game structures, and use it to characterize the worst-case computational complexity of the problem as EXPTIME-complete. Then, we consider the case of deterministic domains and propose a different technique to solve agent planning programs, which is based on iteratively solving classical planning problems and on exploiting goal preferences and plan adaptation methods. Finally, we study the effectiveness of this approach for deterministic domains through an experimental analysis on well-known planning domains.
MSC:
68T42 Agent technology and artificial intelligence
68N19 Other programming paradigms (object-oriented, sequential, concurrent, automatic, etc.)
PDF BibTeX Cite
Full Text: DOI
References:
[1] Alur, R.; Torre, S. L., Deterministic generators and games for LTL fragments, ACM Trans. Comput. Log., 5, 1, 1-25, (2004) · Zbl 1366.03181
[2] Bacchus, F., The AIPS’00 planning competition, AI Mag., 22, 47-56, (2001)
[3] Bacchus, F.; Kabanza, F., Using temporal logics to express search control knowledge for planning, Artif. Intell., 116, 1-2, 123-191, (2000) · Zbl 0939.68827
[4] Bäckström, C.; Nebel, B., Complexity results for SAS+ planning, Comput. Intell., 11, 4, 1-34, (1995)
[5] Baier, J. A.; Fritz, C.; McIlraith, S. A., Exploiting procedural domain control knowledge in state-of-the-art planners, (Proceedings of the International Conference on Automated Planning and Scheduling, ICAPS, (2007)), 26-33
[6] Baier, J. A.; Bacchus, F.; McIlraith, S. A., A heuristic search approach to planning with temporally extended preferences, Artif. Intell., 173, 5-6, 593-618, (2009) · Zbl 1191.68623
[7] Belardinelli, F.; Lomuscio, A.; Patrizi, F., An abstraction technique for the verification of artifact-centric systems, (Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning (KR), (2012)), 319-328
[8] Berardi, D.; Calvanese, D.; De Giacomo, G.; Lenzerini, M.; Mecella, M., Automatic composition of e-services that export their behavior, (Proceedings of the International Conference on Service Oriented Computing, ICSOC, (2003)), 43-58
[9] Bertoli, P.; Pistore, M.; Traverso, P., Automated composition of web services via planning in asynchronous domains, Artif. Intell., 174, 3-4, 316-361, (2010)
[10] Bloem, R.; Cimatti, A.; Greimel, K.; Hofferek, G.; Könighofer, R.; Roveri, M.; Schuppan, V.; Seeber, R., Ratsy - a new requirements analysis tool with synthesis, (Proceedings of the International Conference on Computer Aided Verification, CAV, (2010)), 425-429
[11] Bloem, R.; Jobstmann, B.; Piterman, N.; Pnueli, A.; Sa’ar, Y., Synthesis of reactive(1) designs, J. Comput. Syst. Sci., 78, 3, 911-938, (2012) · Zbl 1247.68050
[12] Blum, A. L.; Furst, M. L., Fast planning through planning graph analysis, Artif. Intell., 90, 1-2, 281-300, (1997) · Zbl 1017.68533
[13] Bonet, B.; Palacios, H.; Geffner, H., Automatic derivation of memoryless policies and finite-state controllers using classical planners, (Proceedings of the International Conference on Automated Planning and Scheduling, ICAPS, (2009)), 190-197
[14] Bratman, M. E., Intentions, plans, and practical reason, (1987), Harvard University Press
[15] Bratman, M. E.; Israel, D. J.; Pollack, M. E., Plans and resource-bounded practical reasoning, Comput. Intell., 4, 3, 349-355, (1988)
[16] Burch, J. R.; Clarke, E. M.; McMillan, K. L.; Dill, D. L.; Hwang, L. J., Symbolic model checking: 10^{20} states and beyond, Inf. Comput., 98, 2, 142-170, (1992) · Zbl 0753.68066
[17] Cavada, R.; Cimatti, A.; Roveri, M.; Schuppan, V.; Tchaltsev, A., (2010), NuGaT game solver home page
[18] Cavazza, M.; Charles, F.; Mead, S. J., Character-based interactive storytelling, IEEE Intell. Syst., 17, 4, 17-24, (2002)
[19] Ceriani, L.; Gerevini, A., Planning with always preferences and soft goals by compilation into STRIPS with action costs, (Proceedings of the 8th International Annual Symposium on Combinatorial Search, (2015)), 161-165
[20] Cimatti, A.; Clarke, E.; Giunchiglia, E.; Giunchiglia, F.; Pistore, M.; Roveri, M.; Sebastiani, R.; Tacchella, A., Nusmv 2: an opensource tool for symbolic model checking, (Proceedings of the International Conference on Computer Aided Verification, CAV, (2002)), 359-364 · Zbl 1010.68766
[21] Cimatti, A.; Clarke, E. M.; Giunchiglia, F.; Roveri, M., NUSMV: a new symbolic model checker, Int. J. Softw. Tools Technol. Transf. (STTT), 2, 4, 410-425, (2000) · Zbl 1059.68582
[22] Cimatti, A.; Roveri, M.; Traverso, P., Automatic OBDD-based generation of universal plans in non-deterministic domains, (Proceedings of the National Conference on Artificial Intelligence, AAAI, (1998)), 875-881
[23] Cohen, P. R.; Levesque, H. J., Intention is choice with commitment, Artif. Intell., 42, 213-261, (1990) · Zbl 0721.03017
[24] Dastani, M., 2APL: a practical agent programming language, Auton. Agents Multi-Agent Syst., 16, 3, 214-248, (Jun. 2008)
[25] Dastani, M.; van Riemsdijk, B.; Meyer, J.-J., Goal types in agent programming, (Proceedings of the International Conference on Autonomous Agents and Multi-Agent Systems, AAMAS, (2006)), 1285-1287
[26] de Boer, F. S.; Hindriks, K. V.; van der Hoek, W.; Meyer, J.-J., A verification framework for agent programming with declarative goals, J. Appl. Log., 5, 2, 277-302, (2007) · Zbl 1122.68078
[27] De Giacomo, G.; Di Ciccio, C.; Felli, P.; Hu, Y.; Mecella, M., Goal-based composition of stateful services for smart homes, (On the Move to Meaningful Internet Systems: OTM 2012, Confederated International Conferences: CoopIS, DOA-SVI, and ODBASE 2012, (2012)), 194-211
[28] De Giacomo, G.; Lespérance, Y.; Levesque, H. J., Congolog, a concurrent programming language based on the situation calculus, Artif. Intell., 121, 1-2, 109-169, (2000) · Zbl 0948.68175
[29] De Giacomo, G.; Lespérance, Y.; Levesque, H. J.; Sardina, S., Indigolog: a high-level programming language for embedded reasoning agents, (Bordini, R. H.; Dastani, M.; Dix, J.; Fallah-Seghrouchni, A. E., Multi-Agent Programming: Languages, Platforms and Applications, (2009), Springer), 31-72, (ch. 2)
[30] De Giacomo, G.; Lespérance, Y.; Patrizi, F., Bounded situation calculus action theories and decidable verification, (Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning (KR), (2012)), 467-477
[31] De Giacomo, G.; Lespérance, Y.; Patrizi, F.; Vassos, S., LTL verification of online executions with sensing in bounded situation calculus, (Proceedings of the European Conference in Artificial Intelligence, ECAI, (2014)), 369-374 · Zbl 1366.68340
[32] De Giacomo, G.; Lespérance, Y.; Patrizi, F.; Vassos, S., Progression and verification of situation calculus agents with bounded beliefs, (Proceedings of the International Conference on Autonomous Agents and Multi-Agent Systems, AAMAS, (2014)), 141-148
[33] De Giacomo, G.; Patrizi, F.; Felli, P.; Sardina, S., Two-player game structures for generalized planning and agent composition, (Proceedings of the National Conference on Artificial Intelligence, AAAI, (2010)), 297-302
[34] De Giacomo, G.; Patrizi, F.; Sardina, S., Agent programming via planning programs, (Proceedings of the International Conference on Autonomous Agents and Multi-Agent Systems, AAMAS, (2010)), 491-498
[35] De Giacomo, G.; Patrizi, F.; Sardina, S., Automatic behavior composition synthesis, Artif. Intell., 196, 106-142, (2013) · Zbl 1270.68329
[36] De Giacomo, G.; Vardi, M. Y., Automata-theoretic approach to planning for temporally extended goals, (Proceedings of the European Conference on Planning, ECP, Lecture Notes in Computer Science, vol. 1809, (1999), Springer), 226-238
[37] Despouys, O.; Ingrand, F. F., Propice-plan: toward a unified framework for planning and execution, (Proceedings of the European Conference on Planning, ECP, Lecture Notes in Computer Science, vol. 1809, (1999), Springer), 278-293
[38] Dijkstra, E. W., A discipline of programming, (1976), Prentice Hall · Zbl 0368.68005
[39] Dix, J.; Muñoz-Avila, H.; Nau, D. S.; Zhang, L., Impacting SHOP: putting an AI planner into a multi-agent environment, Ann. Math. Artif. Intell., 37, 4, 381-407, (2003) · Zbl 1010.68171
[40] Edelkamp, S., On the compilation of plan constraints and preferences, (Proceedings of the International Conference on Automated Planning and Scheduling, ICAPS, (2006)), 374-377
[41] Emerson, E. A., Temporal and modal logic, (van Leeuwen, J., Handbook of Theoretical Computer Science, vol. B, (1990), MIT Press), 995-1072 · Zbl 0900.03030
[42] Floyd, R. W., Nondeterministic algorithms, J. ACM, 14, 4, 636-644, (1967) · Zbl 0153.47006
[43] Gerevini, A.; Haslum, P.; Long, D.; Saetti, A.; Dimopoulos, Y., Deterministic planning in the fifth international planning competition: PDDL3 and experimental evaluation of the planners, Artif. Intell., 173, 5-6, 619-668, (2009) · Zbl 1191.68634
[44] Gerevini, A.; Patrizi, F.; Saetti, A., An effective approach to realizing planning programs, (Proceedings of the International Conference on Automated Planning and Scheduling, ICAPS, (2011)), 323-326
[45] Gerevini, A.; Saetti, A.; Serina, I., Planning through stochastic local search and temporal action graphs, J. Artif. Intell. Res. (JAIR), 20, 239-290, (2003) · Zbl 1058.68103
[46] Ghallab, M.; Nau, D. S.; Traverso, P., Automated planning: theory and practice, (May 2004), Morgan Kaufmann Publishers Inc.
[47] Ghallab, M.; Nau, D. S.; Traverso, P., The Actor’s view of automated planning and acting: a position paper, Artif. Intell., 208, 1-17, (2014)
[48] Ginsberg, M. L., Universal planning: an (almost) universally bad idea, AI Mag., 10, 41-44, (1989)
[49] (Grädel, E.; Thomas, W.; Wilke, T., Automata, Logics, and Infinite Games: A Guide to Current Research, Lecture Notes in Computer Science (LNCS), vol. 2500, (2002), Springer) · Zbl 1011.00037
[50] Hall, K. H.; Staron, R. J.; Vrba, P., Experience with holonic and agent-based control systems and their adoption by industry, (Holonic and Multi-Agent Systems for Manufacturing, Lecture Notes in Computer Science (LNCS), vol. 3593, (2005), Springer), 1-10
[51] Hariri, B. B.; Calvanese, D.; De Giacomo, G.; Deutsch, A.; Montali, M., Verification of relational data-centric dynamic systems with external services, (ACM Symposium on Principles of Database Systems, PODS, (2013)), 163-174
[52] Helal, S.; Mann, W.; El-Zabadani, H.; King, J.; Kaddoura, Y.; Jansen, E., The gator tech smart house: a programmable pervasive space, Computer, 38, 3, (2005)
[53] Helmert, M., The fast downward planning system, J. Artif. Intell. Res. (JAIR), 26, 191-246, (2006) · Zbl 1182.68245
[54] (Helmert, M.; Do, M.; Refanidis, I., Sixth International Planning Competition IPC6: Deterministic Part, (2008))
[55] Hoare, C. A., An axiomatic basis for computer programming, Commun. ACM, 12, 10, (1969) · Zbl 0179.23105
[56] Hoffmann, J.; Edelkamp, S., The deterministic part of IPC-4: an overview, J. Artif. Intell. Res. (JAIR), 24, 519-579, (2005) · Zbl 1080.68669
[57] Hoffmann, J.; Nebel, B., The FF planning system: fast plan generation through heuristic search, J. Artif. Intell. Res. (JAIR), 14, 253-302, (2001) · Zbl 0970.68044
[58] Hübner, J. F.; Bordini, R. H.; Wooldridge, M., Programming declarative goals using plan patterns, (Proceedings of the International Workshop on Declarative Agent Languages and Technologies (DALT), Lecture Notes in Computer Science (LNCS), vol. 4327, (2006), Springer), 123-140
[59] (Jiménez, S.; Coles, A., Seventh International Planning Competition IPC7: Learning Part, (2011))
[60] Jobstmann, B.; Galler, S.; Weiglhofer, M.; Bloem, R., Anzu: a tool for property synthesis, (Proceedings of the International Conference on Computer Aided Verification, CAV, (2007)), 258-262
[61] Kabanza, F.; Thiébaux, S., Search control in planning for temporally extended goals, (Proceedings of the International Conference on Automated Planning and Scheduling, ICAPS, (2005)), 130-139
[62] Keyder, E.; Geffner, H., Soft goals can be compiled away, J. Artif. Intell. Res. (JAIR), 36, 547-556, (2009) · Zbl 1185.68644
[63] Koehler, J.; Nebel, B.; Hoffmann, J.; Dimopoulos, Y., Extending planning graphs to an ADL subset, (1997), Institut für Informatik Freiburg, Germany, Technical Report 88
[64] Kuter, U.; Nau, D. S.; Reisner, E.; Goldman, R. P., Using classical planners to solve nondeterministic planning problems, (Proceedings of the International Conference on Automated Planning and Scheduling, ICAPS, (2008)), 190-197
[65] Lago, U. D.; Pistore, M.; Traverso, P., Planning with a language for extended goals, (Proceedings of the National Conference on Artificial Intelligence, AAAI, (2002)), 447-454
[66] Lespérance, Y.; Levesque, H. J.; Lin, F.; Marcu, D.; Reiter, R.; Scherl, R. B., Foundations of a logical approach to agent programming, (Proceedings of the International Workshop on Agent Theories, Architectures, and Languages, ATAL, (1995)), 331-346
[67] Levesque, H. J.; Reiter, R., High-level robotic control: beyond planning. A position paper, (AIII 1998 Spring Symposium: Integrating Robotics Research: Taking the Next Big Leap, (1998)), 106-108
[68] Levesque, H. J.; Reiter, R.; Lespérance, Y.; Lin, F.; Scherl, R. B., GOLOG: a logic programming language for dynamic domains, J. Log. Program., 31, 59-84, (1997) · Zbl 0880.68008
[69] Littman, M. L., Probabilistic propositional planning: representations and complexity, (Proceedings of the National Conference on Artificial Intelligence, AAAI, (1997)), 748-754
[70] Long, D.; Fox, M., The 3rd international planning competition: results and analysis, J. Artif. Intell. Res. (JAIR), 20, 1-59, (2003) · Zbl 1036.68097
[71] McDermott, D., The 1998 AI planning systems competition, AI Mag., 21, 35-55, (2000)
[72] McIlraith, S. A.; Son, T. C., Adapting golog for composition of semantic web service, (Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning (KR), (2002)), 482-493
[73] McMillan, K. L., Symbolic model checking - an approach to the state explosion problem, (1992), Carnegie Mellon University, TR CMU-CS-92-131
[74] Meyer, B., Applying “design by contract”, IEEE Comput., 25, 10, 40-51, (1992)
[75] Milner, R., An algebraic definition of simulation between programs, (Proceedings of the International Joint Conference on Artificial Intelligence, IJCAI, (1971)), 481-489
[76] Muscholl, A.; Walukiewicz, I., A lower bound on web services composition, (Proceedings of the International Conference on Foundations of Software Science and Computation Structures, FoSSaCS, Lecture Notes in Computer Science (LNCS), vol. 4423, (2007), Springer), 274-286 · Zbl 1195.68067
[77] Nebel, B.; Koehler, J., Plan reuse versus plan generation: a theoretical and empirical analysis, Artif. Intell., 76, 1-2, 427-454, (1995)
[78] Paolucci, M.; Kalp, D.; Pannu, A.; Shehory, O.; Sycara, K., A planning component for RETSINA agents, (Proceedings of the International Workshop on Agent Theories, Architectures, and Languages, ATAL, (1999)), 147-161 · Zbl 0970.68607
[79] Pistore, M.; Traverso, P., Planning as model checking for extended goals in non-deterministic domains, (Proceedings of the International Joint Conference on Artificial Intelligence, IJCAI, (2001)), 479-484
[80] Piterman, N.; Pnueli, A.; Sa’ar, Y., Synthesis of reactive(1) designs, (Proceedings of the International Conference on Verification, Model Checking, and Abstract Interpretation, VMCAI, Lecture Notes in Computer Science (LNCS), vol. 3855, (2006), Springer), 364-380 · Zbl 1176.68126
[81] Pnueli, A., The temporal logic of programs, (Proceedings of the Annual Symposium on Foundations of Computer Science, FOCS, (1977)), 46-57
[82] Pnueli, A.; Rosner, R., On the synthesis of a reactive module, (Proceedings of the ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL, (1989)), 179-190
[83] Pnueli, A.; Sa’ar, Y.; Zuck, L. D., JTLV: a framework for developing verification algorithms, (Proceedings of the International Conference on Computer Aided Verification, CAV, (2010)), 171-174
[84] Pnueli, A.; Shahar, E., A platform for combining deductive with algorithmic verification, (Proceedings of the International Conference on Computer Aided Verification, CAV, (1996)), 184-195
[85] Porteous, J.; Cavazza, M.; Charles, F., Narrative generation through characters’ point of view, (Proceedings of the International Conference on Autonomous Agents and Multi-Agent Systems, AAMAS, (2010)), 1297-1304
[86] Ramirez, M.; Yadav, N.; Sardina, S., Behavior composition as fully observable non-deterministic planning, (Proceedings of the International Conference on Automated Planning and Scheduling, ICAPS, (2013)), 180-188
[87] Rao, A. S., Agentspeak(L): BDI agents speak out in a logical computable language, (Proceedings of the European Workshop on Modeling Autonomous Agents in a Multi-Agent World (Agents Breaking Away), Lecture Notes in Computer Science (LNCS), vol. 1038, (1996), Springer), 42-55
[88] Reiter, R., Knowledge in action. logical foundations for specifying and implementing dynamical systems, (2001), The MIT Press · Zbl 1018.03022
[89] Richter, S.; Westphal, M., The LAMA planner: guiding cost-based anytime planning with landmarks, J. Artif. Intell. Res. (JAIR), 39, 127-177, (2010) · Zbl 1205.68383
[90] Rintanen, J., Complexity of planning with partial observability, (Proceedings of the International Conference on Automated Planning and Scheduling, ICAPS, (2004)), 345-354
[91] Sardina, S.; Padgham, L., A BDI agent programming language with failure recovery, declarative goals, and planning, Auton. Agents Multi-Agent Syst., 23, 1, 18-70, (2011)
[92] Schoppers, M. J., Universal plans for reactive robots in unpredictable environments, (Proceedings of the International Joint Conference on Artificial Intelligence, IJCAI, (1987)), 1039-1046
[93] Shaparau, D.; Pistore, M.; Traverso, P., Fusing procedural and declarative planning goals for nondeterministic domains, (Proceedings of the National Conference on Artificial Intelligence, AAAI, (2008)), 983-990
[94] Shivashankar, V.; Alford, R.; Kuter, U.; Nau, D., The godel planning system: a more perfect union of domain-independent and hierarchical planning, (Proceedings of the International Joint Conference on Artificial Intelligence, IJCAI, (2013), AAAI Press), 2380-2386
[95] Shivashankar, V.; Kuter, U.; Nau, D.; Alford, R., Hierarchical goal-based formalism and algorithm for single-agent planning, (Proceedings of the International Conference on Autonomous Agents and Multi-Agent Systems, AAMAS, (2012)), 981-988
[96] Shivashankar, V.; Kuter, U.; Nau, D., Hierarchical goal network planning: initial results, (2011), University of Maryland Freiburg, Germany, Technical Report CS-TR-4983
[97] Shoham, Y., An overview of agent-oriented programming, (Bradshaw, J. M., Software Agents, (1997), The MIT Press), 271-290
[98] Srivastava, S.; Immerman, N.; Zilberstein, S., A new representation and associated algorithms for generalized planning, Artif. Intell., 175, 2, 615-647, (2011) · Zbl 1216.68253
[99] van der Aalst, W. M.P.; ter Hofstede, A. H.M.; Weske, M., Business process management: a survey, (Proceedings of the International Conference on Business Process Management, BPM, (2003)), 1-12
[100] van Riemsdijk, B.; Dastani, M.; Dignum, F.; Meyer, J.-J., Dynamics of declarative goals in agent programming, (Proceedings of the International Workshop on Declarative Agent Languages and Technologies (DALT), Lecture Notes in Computer Science (LNCS), vol. 3476, (2005), Springer), 1-18
[101] van Riemsdijk, B.; Dastani, M.; Meyer, J.-J., Semantics of declarative goals in agent programming, (Proceedings of the International Conference on Autonomous Agents and Multi-Agent Systems, AAMAS, (2005)), 133-140
[102] Vardi, M. Y., An automata-theoretic approach to linear temporal logic, (Logics for Concurrency: Structure Versus Automata, Lecture Notes in Computer Science (LNCS), vol. 1043, (1996), Springer), 238-266
[103] Walczak, A.; Braubach, L.; Pokahr, A.; Lamersdorf, W., Augmenting BDI agents with deliberative planning techniques, (Proceedings of the Programming Multiagent Systems Languages, Frameworks, Techniques and Tools Workshop, PROMAS, (2006)), 113-127
[104] Wilkins, D. E.; Myers, K. L., A common knowledge representation for plan generation and reactive execution, J. Log. Comput., 5, 6, 731-761, (1995) · Zbl 0960.68669
[105] Wilkins, D. E.; Myers, K. L.; Lowrance, J. D.; Wesley, L. P., Planning and reacting in uncertain and dynamic environments, J. Exp. Theor. Artif. Intell., 7, 1, 197-227, (1995) · Zbl 0939.68834
[106] Williams, B. C.; Ingham, M. D.; Chung, S. H.; Elliott, P. H., Model-based programming of intelligent embedded systems and robotic space explorers, Proc. IEEE, 91, 1, 212-237, (2003), Special Issue on Modeling and Design of Embedded Software
[107] Wolper, P., On the relation of programs and computations to models of temporal logic, (Temporal Logic in Specification, (1987)), 75-123
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.