Sage Journals: Discover world-class research

Abstract

Goal Reasoning (GR) agents operating in partially observable environments need to hypothesize about hidden features in the current state to select an appropriate goal and create a plan to achieve it. The Online Iterative Explanation (OIE) problem is a variant of explanatory diagnosis tailored to the needs of these agents; it requires maintaining a complete plausible hypothetical execution history that is consistent with all previous observations, and which is updated iteratively with each new agent observation. Previous work has proposed and demonstrated a variety of OIE approaches for goal reasoning agents. Our contribution in this work is instead a formal investigation of the OIE solution space, which is the set of all consistent explanations at a given point during execution. This space spans a range of uncertainty (both unimportant and important) about the system’s ground truth execution history and state. We propose formal tools for exploring this space, recognizing its features, and understanding its dynamics over the course of execution. We approach this complex problem through two formalisms, starting with a rigorous formalization in the situation calculus, and followed by an application of a more intuitive state-set framework. This analysis will inform efforts to improve efficiency and reduce risk in future OIE algorithms.

Keywords

Explanation diagnosis goal reasoning situation calculus

Get full access to this article

View all access options for this article.

References

Bonet and

Geffner, Planning with incomplete information as heuristic search in belief space, in: Proceedings of the Fifth International Conference on Artificial Intelligence Planning Systems, AAAI Press, 2000.

M.T.

Cox,

Alavi,

Dannenhauer,

Eyorokon,

Munoz-Avila and

Perlis, Midca: A metacognitive, integrated dual-cycle architecture for self-regulated autonomy, in: Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, AAAI Press, 2016.

R.L.

de Mántaras,

McSherry,

Bridge,

Leake,

Smyth,

Craw,

Faltings,

M.L.

Maher,

M.T.

Cox,

Forbus,

Keane,

Aamodt and

Watson, Retrieval, reuse and retention in case-based reasoning, Knowledge Engineering Review20(3) (2006), 215–240.

Hoffman and

Brafman, Contingent planning via heuristic forward search with implicit belief states, in: Proceedings of the International Conference on Artificial Intelligence Planning Systems, AAAI Press, 2005.

Johnson,

M.W.

Floyd,

Coman,

M.A.

Wilson and

D.W.

Aha, Goal reasoning and trusted autonomy, in: Foundations of Trusted Autonomy,

H.A.

Abbass,

J.B.

Scholz and

D.J.

Reid, eds, Springer, 2017.

R.E.

Kalman, A new approach to linear filtering and prediction problems, Journal of Basic Engineering82(1) (1960), 35–45. doi:10.1115/1.3662552.

J.D.

Kleer, An assumption-based TMS, Artificial Intelligence28(2) (1986), 127–162. doi:10.1016/0004-3702(86)90080-9.

J.L.

Kolodner, Case-Based Reasoning, Morgan Kaufmann, San Francisco, CA, 1993.

Lin and

Reiter, State constraints revisited, Journal of Logic and Computation4(5) (1994), 655–678. doi:10.1093/logcom/4.5.655.

10.

McCarthy and

Hayes, Some philosophical problems from the standpoint of artificial intelligence, Machine Intelligence4 (1969), 463–502.

11.

McIlraith, Towards a formal account of diagnostic problem solving, PhD thesis, University of Toronto, Toronto, Ontario, Canada, 1997.

12.

Mcllraith, Explanatory diagnosis: Conjecturing actions to explain observations, in: Logical Foundations for Cognitive Agents, Springer, 1999, pp. 155–172. doi:10.1007/978-3-642-60211-5_13.

13.

Molineaux and

D.W.

Aha, Learning unknown event models, in: Proceedings of the 28th AAAI Conference on Artificial Intelligence, AAAI Press, Quebec City, Quebec, Canada, 2014.

14.

Molineaux and

D.W.

Aha, Continuous explanation generation in a multi-agent domain, in: Proceedings of the Third Conference on Advances in Cognitive Systems, Atlanta, GA, 2015, Cognitive Systems Foundation.

15.

Molineaux,

Kuter and

Klenk, DiscoverHistory: Understanding the past in planning and execution, in: Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems, Valencia, Spain, 2012, International Foundation for Autonomous Agents and Multiagent Systems.

16.

M.K.M.

Molineaux and

D.W.

Aha, Goal-driven autonomy in a Navy strategy simulation, in: Proceedings of the 24th AAAI Conference on Artificial Intelligence, AAAI Press, Atlanta, GA, 2010.

17.

Pang and

R.C.

Holte, State-set search, in: Fourth Annual Symposium on Combinatorial Search, AAAI Press, Barcelona, Spain, 2011.

18.

Reiter, A theory of diagnosis from first principles, Artificial Intelligence32(1) (1987), 57–95. doi:10.1016/0004-3702(87)90062-2.

19.

Sampath,

Sengupta,

Lafortune,

Sinnamohideen and

D.C.

Teneketzis, Failure diagnosis using discrete-event models, IEEE Transactions on Control Systems Technology4(2) (1996), 105–124. doi:10.1109/87.486338.

20.

J.A.B.

Shirin Sohrabi and

McIlraith, Diagnosis as planning revisited, in: Proceedings of the 12th International Conference on the Principles of Knowledge Representation and Reasoning, AAAI Press, Toronto, Ontario, Canada, 2010.

21.

Sohrabi,

J.A.

Baier and

McIlraith, Preferred explanations: Theory and generation via planning, in: Proceedings of the 25th AAAI Conference on Artificial Intelligence, AAAI Press, San Francisco, CA, 2011.

22.

Sohrabi,

Udrea and

A.V.

Riabov, Hypothesis exploration for malware detection using planning, in: Proceedings of the 27th AAAI Conference on Artificial Intelligence, AAAI Press, Bellevue, Washington, 2013.

23.

M.M.

Swaroop,

Vattam,

Klenk and

D.W.

Aha, Breadth of approaches to goal reasoning: A research survey, in: Goal Reasoning: Papers from the ACS Workshop, Baltimore, Maryland, 2013.

24.

Thrun,

Burgard and

Fox, Probabilistic Robotics, MIT Press, Cambridge, MA, 2005.

25.

Travé-Massuyès, Bridging control and artificial intelligence theories for diagnosis: A survey, Engineering Applications of Artificial Intelligence27 (2014), 1–16. doi:10.1016/j.engappai.2013.09.018.

26.

Yu,

Wen and

Liu, Multi-agent epistemic explanatory diagnosis via reasoning about actions, in: Proceedings of the 23rd International Joint Conference on Artificial Intelligence, AAAI Press, Beijing, China, 2013.

Investigating the solution space for online iterative explanation in goal reasoning agents

Abstract

Keywords

Get full access to this article

References