A history based approximate epistemic action theory for efficient postdictive reasoning.

*(English)*Zbl 1457.68256Summary: We propose an approximation of the possible worlds semantics (\(\mathcal{PWS}\)) of knowledge with support for postdiction – a fundamental inference pattern for diagnostic reasoning and explanation tasks in a wide range of real-world applications such as cognitive robotics, visual perception for cognitive vision, ambient intelligence and smart environments. We present the formal framework, an operational semantics, and an analysis of soundness and completeness results therefrom.

The advantage of our approach is that only a linear number of state-variables are required to represent an agent’s knowledge state. This is achieved by modeling knowledge as the history of a single approximate state, instead of using an exponential number of possible worlds like in Kripke semantics. That is, we add a temporal dimension to the knowledge representation which facilitates efficient postdiction. Since we consider knowledge histories, we call our theory \(h\)-approximation (\(\mathcal{HPX}\)).

Due to the linear number of state variables, \(\mathcal{HPX}\) features a comparably low computational complexity. Specifically, we show that \(\mathcal{HPX}\) can solve the projection problem in polynomial (tractable) time. It can solve planning problems in NP, while e.g. for the action language \(\mathcal{A}_k\) [T. C. Son and C. Baral, Artif. Intell. 125, No. 1–2, 19–91 (2001; Zbl 0969.68152)] this is \({\Sigma}_2^P\)-complete. In addition to the temporal dimension of knowledge, our theory supports concurrent acting and sensing, and is in this sense more expressive than existing approximations.

The advantage of our approach is that only a linear number of state-variables are required to represent an agent’s knowledge state. This is achieved by modeling knowledge as the history of a single approximate state, instead of using an exponential number of possible worlds like in Kripke semantics. That is, we add a temporal dimension to the knowledge representation which facilitates efficient postdiction. Since we consider knowledge histories, we call our theory \(h\)-approximation (\(\mathcal{HPX}\)).

Due to the linear number of state variables, \(\mathcal{HPX}\) features a comparably low computational complexity. Specifically, we show that \(\mathcal{HPX}\) can solve the projection problem in polynomial (tractable) time. It can solve planning problems in NP, while e.g. for the action language \(\mathcal{A}_k\) [T. C. Son and C. Baral, Artif. Intell. 125, No. 1–2, 19–91 (2001; Zbl 0969.68152)] this is \({\Sigma}_2^P\)-complete. In addition to the temporal dimension of knowledge, our theory supports concurrent acting and sensing, and is in this sense more expressive than existing approximations.

Reviewer: Reviewer (Berlin)

##### MSC:

68T27 | Logic in artificial intelligence |

68Q25 | Analysis of algorithms and problem complexity |

68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |

68T30 | Knowledge representation |

##### Software:

PDDL
PDF
BibTeX
XML
Cite

\textit{M. Eppe} and \textit{M. Bhatt}, J. Appl. Log. 13, No. 4, Part 3, 720--769 (2015; Zbl 1457.68256)

Full Text:
DOI

##### References:

[1] | Bäckström, C.; Nebel, B., Complexity results for SAS+ planning, Comput. Intell., 11, 625-655, (1995) |

[2] | Baral, C., Knowledge representation, reasoning and declarative problem solving, (2003), Cambridge University Press · Zbl 1056.68139 |

[3] | Baral, C.; Kreinovich, V.; Trejo, R., Computational complexity of planning and approximate planning in the presence of incompleteness, Artif. Intell., 122, 241-267, (2000) · Zbl 0948.68088 |

[4] | Bertoli, P.; Cimatti, A.; Pistore, M.; Roveri, M.; Traverso, P., MBP: a model based planner, (Proceedings of the International Joint Conference on Artificial Intelligence, (2001)) |

[5] | Bhatt, M.; Wallgruen, J. O., Geospatial narratives and their spatio-temporal dynamics: commonsense reasoning for high-level analyses in geographic information systems, (Rocchini, D., ISPRS International Journal of Geo-Information; Special Issue on: Geospatial Monitoring and Modelling of Environmental Change, (2013)), arXiv - Cornell University Library (draft available on arXiv) |

[6] | Bonet, B.; Geffner, H., Planning under partial observability by classical replanning: theory and experiments, (IJCAI Proceedings, (2011)) |

[7] | Brachman, R. J.; Levesque, H. J., Knowledge representation and reasoning, (2004), Elsevier |

[8] | Carnap, R., Meaning and necessity: A study in semantics and modal logic, (1956), The University of Chicago Press · Zbl 0034.00106 |

[9] | Cimatti, A.; Pistore, M.; Roveri, M.; Traverso, P., Weak, strong, and strong cyclic planning via symbolic model checking, Artif. Intell., 147, 35-84, (2003) · Zbl 1082.68800 |

[10] | Davis, E., Representations of common sense knowledge, The Morgan Kaufmann Series in Representation and Reasoning, (1990), Elsevier Science Limited |

[11] | Demolombe, R.; del Pilar Pozos Parra, M., A simple and tractable extension of situation calculus to epistemic logic, (International Symposium on Foundations of Intelligent Systems, (2000)) · Zbl 0983.68187 |

[12] | van Ditmarsch, H.; van der Hoek, W.; Kooi, B., Dynamic epistemic logic, (2007), Springer · Zbl 1156.03320 |

[13] | Eppe, M.; Bhatt, M., Narrative based postdictive reasoning for cognitive robotics, (11th International Symposium on Logical Formalizations of Commonsense Reasoning, (2013)) |

[14] | Eppe, M.; Bhatt, M., Approximate postdictive reasoning with answer set programming, J. Appl. Log., 13, 676-719, (2015), in this issue · Zbl 1457.68255 |

[15] | Eppe, M.; Bhatt, M.; Dylla, F., Approximate epistemic planning with postdiction as answer-set programming, (Proceedings of the 12th International Conference on Logic Programming and Nonmonotonic Reasoning, (2013)) · Zbl 1405.68348 |

[16] | Fagin, R.; Halpern, J. Y.; Moses, Y.; Vardi, M. Y., Reasoning about knowledge, (1995), MIT Press · Zbl 0839.68095 |

[17] | Fikes, R.; Nilsson, N., STRIPS: a new approach to the application of theorem proving to problem solving, Artif. Intell., 2, 189-208, (1971) · Zbl 0234.68036 |

[18] | de Giacomo, G.; Levesque, H. J., An incremental interpreter for high-level programs with sensing, (Working Notes of the 1998 AAAI Fall Symposium on Cognitive Robotics, (1998)) |

[19] | Hanks, S.; McDermott, D., Nonmonotonic logic and temporal projection, Artif. Intell., 33, 379-412, (1987) · Zbl 0654.68107 |

[20] | van Harmelen, F.; van Harmelen, F.; Lifschitz, V.; Porter, B., Handbook of knowledge representation, (2007), Elsevier Science San Diego, USA |

[21] | Hintikka, J., Logic and belief: an introduction to the logic of the two notions, (1962), Cornell University Press Ithaca |

[22] | Hoffmann, J.; Brafman, R. I., Contingent planning via heuristic forward search with implicit belief states, (Proceedings of the International Conference on Automated Planning and Scheduling, (2005)) |

[23] | Hölldobler, S.; Schneeberger, J., A new deductive approach to planning, New Gener. Comput., 8, 225-244, (1990) · Zbl 0711.68026 |

[24] | Kahramanogullari, O.; Thielscher, M., A formal assessment result for fluent calculus using the action description language \(\mathcal{A}_k\), (German Conference on Artificial Intelligence, (2003)) · Zbl 1274.68460 |

[25] | Kowalski, R.; Sergot, M., A logic-based calculus of events, New Gener. Comput., 4, 67-94, (1986) · Zbl 1356.68221 |

[26] | Kripke, S., Semantical considerations on modal logic, Acta Philos. Fenn., 16, 83-94, (1963) · Zbl 0131.00602 |

[27] | Lakemeyer, G.; Levesque, H. J., AOL: a logic of acting, sensing, knowing, and only knowing, (Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning, (1998)) |

[28] | Levesque, H. J., All I know: a study in autoepistemic logic, Artif. Intell., 43, 263-309, (1990) · Zbl 0724.03019 |

[29] | Liu, Y.; Levesque, H. J., Tractable reasoning with incomplete first-order knowledge in dynamic systems with context-dependent actions, (International Joint Conference on Artificial Intelligence, (2005)) |

[30] | Lobo, J.; Mendez, G.; Taylor, S., Knowledge and the action description language A, Theory Pract. Log. Program., 1, 129-184, (2001) · Zbl 1091.68603 |

[31] | Ma, J.; Miller, R.; Morgenstern, L.; Patkos, T., An epistemic event calculus for ASP-based reasoning about knowledge of the past, present and future, (International Conference on Logic for Programming, Artificial Intelligence and Reasoning, (2013)) |

[32] | McCarthy, J., Situations, actions and causal laws, (July 1963), Technical report, Stanford Artificial Intelligence Project |

[33] | McCarthy, J., Elaboration tolerance, (International Symposium on Logical Formalizations of Commonsense Reasoning, (1998)) |

[34] | McDermott, D.; Ghallab, M.; Howe, A.; Knoblock, C.; Ram, A.; Veloso, M.; Wilkins, D., PDDL - the planning domain definition language, (1998), Yale Center for Computational Vision and Control, Technical report |

[35] | Miller, R.; Morgenstern, L.; Patkos, T., Reasoning about knowledge and action in an epistemic event calculus, (International Symposium on Logical Formalizations of Commonsense Reasoning, (2013)) |

[36] | Moore, R. C., A formal theory of knowledge and action, (Hobbs, J.; Moore, R. C., Formal Theories of the Commonsense World, (1985), Ablex Norwood, NJ) |

[37] | Mueller, E., Commonsense reasoning, (2005), Morgan Kaufmann |

[38] | Muise, C.; Belle, V.; McIlraith, S., Computing contingent plans via fully observable non-deterministic planning, (AAAI Conference on Artificial Intelligence, (2014)) |

[39] | Muise, C.; McIlraith, S. A.; Beck, J. C., Improved non-deterministic planning by exploiting state relevance, (22nd International Conference on Automated Planning and Scheduling, ICAPS, (2012)), 172-180 |

[40] | Patkos, T.; Plexousakis, D., Reasoning with knowledge, action and time in dynamic and uncertain domains, (Proceedings of the International Joint Conference on Artificial Intelligence, (2009)) |

[41] | Patkos, T.; Plexousakis, D., Epistemic and causal commonsense reasoning in partially observable dynamic domains - from sensors to concepts, (Bridges Between the Methodological and Practical Work of the Robotics and Cognitive Systems Communities, (2012), Springer) |

[42] | Petrick, R. P.; Bacchus, F., Extending the knowledge-based approach to planning with incomplete information and sensing, (Proceedings of the International Conference on Automated Planning and Scheduling, (2004)) |

[43] | Petrick, R. P.A.; Levesque, H. J., Knowledge equivalence in combined action theories, (Principles of Knowledge Representation and Reasoning, (2002)) |

[44] | Rintanen, J., Complexity of planning with partial observability, (International Conference on Automated Planning and Scheduling, ICAPS, (2004)) |

[45] | Sardina, S.; de Giacomo, G.; Lespérance, Y.; Levesque, H., On the limits of planning over belief states under strict uncertainty, (Principles of Knowledge Representation and Reasoning, (2006)) |

[46] | Sardina, S.; de Giacomo, G.; Lespérance, Y.; Levesque, H. J., On the semantics of deliberation in indigolog - from theory to implementation, Ann. Math. Artif. Intell., 41, 259-299, (2004) · Zbl 1048.68100 |

[47] | Scherl, R. B.; Levesque, H. J., Knowledge, action, and the frame problem, Artif. Intell., 144, 1-39, (2003) · Zbl 1079.68625 |

[48] | Son, T. C.; Baral, C., Formalizing sensing actions - a transition function based approach, Artif. Intell., 125, 19-91, (2001) · Zbl 0969.68152 |

[49] | Thielscher, M., Introduction to the fluent calculus, Linköp. Electron. Artic. Comput. Inf. Sci., 3, (1998) |

[50] | Thielscher, M., Representing the knowledge of a robot, (Cohn, A.; Giunchiglia, F.; Selman, B., Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning (KR), (2000), Morgan Kaufmann Breckenridge, CO), 109-120 |

[51] | Thielscher, M., The concurrent, continuous fluent calculus, Stud. Log., 67, 315-331, (2001) · Zbl 0981.03036 |

[52] | Thielscher, M., FLUX: a logic programming method for reasoning agents, Theory Pract. Log. Program., 5, (2005) · Zbl 1105.68333 |

[53] | To, S. T., On the impact of belief state representation in planning under uncertainty, (Proceedings of the International Joint Conference on Artificial Intelligence, (2011)) |

[54] | To, S. T., A new approach to contingent planning using a disjunctive representation in AND/OR forward search with novel pruning techniques, J. Artif. Intell. Res., (2012) |

[55] | Tu, P. H.; Son, T. C.; Baral, C., Reasoning and planning with sensing actions, incomplete information, and static causal laws using answer set programming, Theory Pract. Log. Program., 7, 377-450, (2007) · Zbl 1120.68101 |

[56] | Vlaeminck, H.; Vennekens, J.; Denecker, M., A general representation and approximate inference algorithm for sensing actions, (Advances in Artificial Intelligence - Australasian Joint Conference, (2012)) |

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.