×

zbMATH — the first resource for mathematics

Asynchronous knowledge with hidden actions in the situation calculus. (English) Zbl 1328.68213
Summary: We present a powerful new account of multi-agent knowledge in the situation calculus and an automated reasoning procedure for knowledge queries. Existing accounts of epistemic reasoning in the situation calculus require that whenever an action occurs, all agents know that an action has occurred. This demands a level of synchronicity that is unreasonable in many multi-agent domains. In asynchronous domains, each agent’s knowledge must instead account for arbitrarily-long sequences of hidden actions. By using a persistence condition meta-operator to augment traditional regression techniques, we show how agents can reason about their own knowledge using only their internal history of observations, rather than requiring a full history of the world. The result is a more robust and flexible account of knowledge in the situation calculus suitable for asynchronous, partially-observable multi-agent domains.

MSC:
68T27 Logic in artificial intelligence
Software:
GOLOG; leanTAP
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bart, Bradley; Delgrande, James P.; Schulte, Oliver, Knowledge and planning in an action-based multi-agent framework: a case study, (Advances in Artificial Intelligence, LNAI, vol. 2056, (2001), Springer), 121-130 · Zbl 0984.68517
[2] Batlag, Alexandru; Moss, Lawrence S.; Solecki, Slawomir, The logic of public announcements and common knowledge and private suspicions, (Proceedings of the 7th Conference on Theoretical Aspects of Rationality and Knowledge, TARK’98, (1998)), 43-56
[3] Beckert, Bernhard; Posegga, Joachim, Leant^AP: Lean tableaue-based deduction, J. Autom. Reason., 15, 339-358, (1995) · Zbl 0838.68097
[4] Claßen, Jens; Lakemeyer, Gerhard, A logic for non-terminating golog programs, (Proceedings of the 11th International Conference on Principles of Knowledge Representation and Reasoning, KR’08, (2008)), 589-599
[5] Cohen, Philip R.; Levesque, Hector J., Intention is choice with commitment, Artif. Intell., 42, 2, 213-261, (1990) · Zbl 0721.03017
[6] De Giacomo, Giuseppe; Reiter, Raymond; Soutchanski, Mikhail, Execution monitoring of high-level robot programs, (Proceedings of the 6th International Conference on Principles of Knowledge Representation and Reasoning, KR’98, (1998)), 453-465
[7] De Giacomo, Giuseppe; Lespérance, Yeves; Patrizi, Fabio, Bounded situation calculus action theories and decidable verification, (Proceedings of the 13th International Conference on Principles of Knowledge Representation and Reasoning, KR’12, (2012)), 467-477
[8] Delgrande, James P.; Hunter, Aaron; Grote, Torsten, On the representation and verification of cryptographic protocols in a theory of action, (2010 Eighth Annual International Conference on Privacy Security and Trust (PST), (2010), IEEE), 39-45
[9] Demolombe, Robert; del Pilar Pozos Parra, Maria, A simple and tractable extension of situation calculus to epistemic logic, (Proceedings of the 12th International Symposium on Foundations of Intelligent Systems, ISMIS’00, (2000)), 515-524 · Zbl 0983.68187
[10] Fagin, Ronald; Halpern, Joseph Y.; Moses, Yoram; Vardi, Moshe Y., Reasoning about knowledge, (1995), The MIT Press Cambridge, Massachusetts · Zbl 0839.68095
[11] Fitting, Melvin, Leant^AP revisited, J. Log. Comput., 8, 1, 33-47, (1998) · Zbl 0909.03013
[12] Fritz, Christian; Baier, Jorge A.; McIlraith, Sheila A., Congolog, sin trans: compiling congolog into basic action theories for planning and beyond, (Proceedings of the 11th International Conference on Principles of Knowledge Representation and Reasoning, KR’08, (2008)), 600-610
[13] Ghaderi, Hojjat; Levesque, Hector; Lespérance, Yves, A logical theory of coordination and joint ability, (Proceedings of the 22nd AAAI Conference on Artificial Intelligence, AAAI’07, (2007)), 421-426 · Zbl 1341.68283
[14] Halpern, J. Y.; Moses, Y., A guide to completeness and complexity for modal logics of knowledge and belief, Artif. Intell., 54, 319-379, (1992) · Zbl 0762.68029
[15] Halpern, Joseph Y.; Moses, Yoram, Knowledge and common knowledge in a distributed environment, J. ACM, 37, 3, 549-587, (1990) · Zbl 0699.68115
[16] Kelly, Ryan F.; Pearce, Adrian R., Towards high-level programming for distributed problem solving, (Proceedings of the IEEE/WIC/ACM International Conference on Intelligent Agent Technology, IAT’06, (2006)), 490-497
[17] Kelly, Ryan F.; Pearce, Adrian R., Knowledge and observations in the situation calculus, (Proceedings of the 6th International Joint Conference on Autonomous Agents and Multi-Agent Systems, AAMAS’07, (2007)), 841-843
[18] Kelly, Ryan F.; Pearce, Adrian R., Complex epistemic modalities in the situation calculus, (Proceedings of the 11th International Conference on Principles of Knowledge Representation and Reasoning, KR’08, (2008)), 611-620
[19] Kelly, Ryan F.; Pearce, Adrian R., Property persistence in the situation calculus, Artif. Intell., 174, 865-888, (2010) · Zbl 1205.68398
[20] Lakemeyer, Gerhard; Lespérance, Yves, Efficient reasoning in multiagent epistemic logics, (Proceedings of the 20th Biennial European Conference on Artificial Intelligence, ECAI’12, (2012)), 498-503 · Zbl 1327.68255
[21] Lespérance, Y.; Levesque, H. J.; Reiter, R., A situation calculus approach to modeling and programming agents, (Rao, A.; Wooldridge, M., Foundations and Theories of Rational Agency, (1999), Kluwer), 275-299 · Zbl 0968.68152
[22] Lespérance, Y.; Levesque, H. J.; Lin, F.; Scherl, R. B., Ability and knowing how in the situation calculus, Stud. Log., 66, 1, 165-186, (October 2000)
[23] Lespérance, Yves, On the epistemic feasibility of plans in multiagent systems specifications, (Proceedings of the 8th International Workshop on Agent Theories, Architectures, and Languages, Lecture Notes in Artificial Intelligence, vol. 2333, (2001)), 69-85 · Zbl 1050.68141
[24] Levesque, Hector J.; Reiter, Ray; Lespérance, Yves; Lin, Fangzhen; Scherl, Richard B., GOLOG: a logic programming language for dynamic domains, J. Log. Program., 31, 1-3, 59-83, (1997) · Zbl 0880.68008
[25] Lin, F.; Levesque, H., What robots can do: robot programs and effective achievability, Artif. Intell., 101, 201-226, (1998) · Zbl 0909.68176
[26] Lin, Fangzhen; Reiter, Ray, State constraints revisited, J. Log. Comput., 4, 5, 655-678, (1994) · Zbl 0815.68096
[27] Lin, Fangzhen; Reiter, Ray, How to progress a database, Artif. Intell., 92, 131-167, (1997) · Zbl 1017.68510
[28] McCarthy, John; Hayes, Patrick J., Some philosophical problems from the standpoint of artificial intelligence, (Meltzer, B.; Michie, D., Machine Intelligence, vol. 4, (1969), Edinburgh University Press), 463-502 · Zbl 0226.68044
[29] Moore, Robert C., Reasoning about knowledge and action, (October 1980), SRI International, Technical note 191
[30] Parikh, Rohit; Ramanujam, R., Distributed processes and the logic of knowledge, (Proceedings of the Conference on Logic of Programs, (1985), Springer-Verlag), 256-268 · Zbl 0565.68025
[31] Petrick, Ron; Levesque, Hector, Knowledge equivalence in combined action theories, (Proceedings of the 8th International Conference on Principles of Knowledge Representation and Reasoning, KR’02, (2002)), 303-314
[32] Petrick, Ronald P. A., A knowledge-level approach for effective acting, sensing, and planning, (2006), Department of Computer Science, University of Toronto Toronto, Ontario, Canada, PhD thesis
[33] Petrick, Ronald P. A., Cartesian situations and knowledge decomposition in the situation calculus, (Proceedings of the 11th International Conference on Principles of Knowledge Representation and Reasoning, KR’08, (2008)), 629-639
[34] Pinto, Javier, Concurrent actions and interacting effects, (Proceedings of the Sixth International Conference on Principles of Knowledge Representation and Reasoning, KR’98, (1998)), 292-303
[35] Pinto, Javier, Concurrency and action interaction, (2000), Technical report
[36] Pinto, Javier A., Temporal reasoning in the situation calculus, (1994), Department of Computer Science, University of Toronto Toronto, Ontario, Canada, PhD thesis
[37] Pirri, Fiora; Reiter, Ray, Some contributions to the metatheory of the situation calculus, J. ACM, 46, 3, 325-361, (1999) · Zbl 1065.68627
[38] Reiter, Ray, The frame problem in situation the calculus: a simple solution (sometimes) and a completeness result for goal regression, (Lifschitz, Vladimir, Artificial Intelligence and Mathematical Theory of Computation: Papers in Honor of John McCarthy, (1991), Academic Press Professional, Inc.), 359-380 · Zbl 0755.68124
[39] Reiter, Ray, Proving properties of states in the situation calculus, Artif. Intell., 64, 337-351, (1993) · Zbl 0788.68139
[40] Reiter, Ray, Natural actions, concurrency and continuous time in the situation calculus, (Proceedings of the 5th International Conference on Principles of Knowledge Representation and Reasoning, KR’96, (1996)), 2-13
[41] Russell, Stuart; Norvig, Peter, Artificial intelligence: A modern approach, (2010), Prentice Hall · Zbl 0835.68093
[42] Sardina, Sebastian; Vassos, Stavros, The wumpus world in indigolog: a preliminary report, (Proceedings of the Workshop on Non-monotonic Reasoning, Action and Change at IJCAI, NRAC-05, (2005)), 90-95
[43] Savelli, Francesco, Existential assertions and quantum levels on the tree of the situation calculus, Artif. Intell., 170, 6, 643-652, (2006) · Zbl 1131.68108
[44] Scherl, Richard, Reasoning about the interaction of knowledge, time and concurrent actions in the situation calculus, (Proceedings of the 18th International Joint Conference on Artificial Intelligence, IJCAI’03, (2003)), 1091-1098
[45] Scherl, Richard; Levesque, Hector, Knowledge, action, and the frame problem, Artif. Intell., 144, 1-39, (2003) · Zbl 1079.68625
[46] Schiffel, S.; Thielscher, M., Reconciling situation calculus and fluent calculus, (Proceedings of the 21st National Conference on Artificial Intelligence and the 18th Innovative Applications of Artificial Intelligence Conference, AAAI’06/IAAI’06, (2006)), 287-292
[47] Shapiro, S.; Pagnucco, M., Iterated belief change and exogenous actions in the situation calculus, (Proceedings of the 16th European Conference on Artificial Intelligence, ECAI’04, (2004)), 878-882
[48] Shapiro, S.; Lespérance, Y.; Levesque, H. J., Specifying communicative multi-agent systems, (Agents and Multi-Agent Systems - Formalisms, Methodologies, and Applications, Lecture Notes in Artificial Intelligence, vol. 1441, (1998)), 1-14
[49] Shapiro, S.; Lesperance, Y.; Levesque, H., Goal change in the situation calculus, J. Log. Comput., 17, 983-1018, (2007) · Zbl 1132.68054
[50] Shapiro, Steven; Lespérance, Yves, Modeling multiagent systems with the cognitive agents specification language — a feature interaction resolution application, (Intelligent Agents Volume VII — Proceedings of the 2000 Workshop on Agent Theories, Architectures, and Languages, (2001), Springer-Verlag), 244-259 · Zbl 1056.68570
[51] Shapiro, Steven; Pagnucco, Maurice; Lespérance, Yves; Levesque, Hector J., Iterated belief change in the situation calculus, (Proceedings of the 7th International Conference on Principles of Knowledge Representation and Reasoning, KR’00, (2000)), 527-538 · Zbl 1216.68275
[52] Shapiro, Steven; Lespérance, Yves; Levesque, Hector J., The cognitive agents specification language and verification environment for multiagent systems, (Proceedings of the 1st International Joint Conference on Autonomous Agents and Multi-Agent Systems, AAMAS’02, (2002)), 19-26
[53] Thielscher, M., A unifying action calculus, Artif. Intell., 175, 1, 120-141, (2011) · Zbl 1216.68277
[54] van Benthem, Johan, Modal logic meets situation calculus, (2007), University of Amsterdam, Technical report PP-2007-04
[55] van Benthem, Johan; Pacuit, Eric, The tree of knowledge in action: towards a common perspective, (Advances in Modal Logic, vol. 6, (2006)), 87-106 · Zbl 1148.03009
[56] van Benthem, Johan; van Eijck, Jan; Kooi, Barteld, Logics of communication and change, Inf. Comput., 204, II, 1620-1662, (2006) · Zbl 1120.03012
[57] van Ditmarsch, Hans; Herzig, Andreas; de Lima, Tiago, Optimal regression for reasoning about knowledge and actions, (Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence, (2007)), 1070-1075
[58] Vassos, Stavros; Levesque, Hector, On the progression of situation calculus basic action theories: resolving a 10-year-old conjecture, (Proceedings of the 23rd AAAI Conference on Artificial Intelligence, AAAI’08, (2008)), 1004-1009
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.