1
|
Pereira RF, Fuggitti F, Meneguzzi F, De Giacomo G. Temporally extended goal recognition in fully observable non-deterministic domain models: Temporally extended goal recognition in FOND planning. APPL INTELL 2023; 54:470-489. [PMID: 38225993 PMCID: PMC10787694 DOI: 10.1007/s10489-023-05087-1] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Grants] [Track Full Text] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Accepted: 10/05/2023] [Indexed: 01/17/2024]
Abstract
Goal Recognition is the task of discerning the intended goal that an agent aims to achieve, given a set of goal hypotheses, a domain model, and a sequence of observations (i.e., a sample of the plan executed in the environment). Existing approaches assume that goal hypotheses comprise a single conjunctive formula over a single final state and that the environment dynamics are deterministic, preventing the recognition of temporally extended goals in more complex settings. In this paper, we expand goal recognition to temporally extended goals in Fully Observable Non-Deterministic (fond) planning domain models, focusing on goals on finite traces expressed in Linear Temporal Logic (ltlf ) and Pure-Past Linear Temporal Logic (ppltl). We develop the first approach capable of recognizing goals in such settings and evaluate it using different ltlf and ppltl goals over six fond planning domain models. Empirical results show that our approach is accurate in recognizing temporally extended goals in different recognition settings.
Collapse
Affiliation(s)
| | - Francesco Fuggitti
- IBM Research AI, Cambridge, USA
- Sapienza University, Rome, Italy
- York University, Toronto, Canada
| | | | | |
Collapse
|
2
|
Fang Z, Chen D, Zeng Y, Wang T, Xu K. Real-Time Online Goal Recognition in Continuous Domains via Deep Reinforcement Learning. ENTROPY (BASEL, SWITZERLAND) 2023; 25:1415. [PMID: 37895536 PMCID: PMC10606411 DOI: 10.3390/e25101415] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Grants] [Track Full Text] [Subscribe] [Scholar Register] [Received: 08/30/2023] [Revised: 09/23/2023] [Accepted: 10/03/2023] [Indexed: 10/29/2023]
Abstract
The problem of goal recognition involves inferring the high-level task goals of an agent based on observations of its behavior in an environment. Current methods for achieving this task rely on offline comparison inference of observed behavior in discrete environments, which presents several challenges. First, accurately modeling the behavior of the observed agent requires significant computational resources. Second, continuous simulation environments cannot be accurately recognized using existing methods. Finally, real-time computing power is required to infer the likelihood of each potential goal. In this paper, we propose an advanced and efficient real-time online goal recognition algorithm based on deep reinforcement learning in continuous domains. By leveraging the offline modeling of the observed agent's behavior with deep reinforcement learning, our algorithm achieves real-time goal recognition. We evaluate the algorithm's online goal recognition accuracy and stability in continuous simulation environments under communication constraints.
Collapse
Affiliation(s)
| | | | | | | | - Kai Xu
- College of Systems Engineering, National University of Defense Technology, Changsha 410000, China; (Z.F.); (D.C.); (Y.Z.); (T.W.)
| |
Collapse
|
3
|
Garrido A. Learning cost action planning models with perfect precision via constraint propagation. Inf Sci (N Y) 2023. [DOI: 10.1016/j.ins.2023.01.111] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 02/01/2023]
|
4
|
Intention Recognition for Multiple Agents. Inf Sci (N Y) 2023. [DOI: 10.1016/j.ins.2023.01.066] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 01/22/2023]
|
5
|
Cardoso RC, Logan B, Meneguzzi F, Oren N, Yun B. Resilience, reliability, and coordination in autonomous multi-agent systems. AI COMMUN 2022. [DOI: 10.3233/aic-220136] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.5] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 01/09/2023]
Abstract
Multi-agent systems is an evolving discipline that encompasses many different branches of research. The long-standing Agents at Aberdeen ( A 3 ) group undertakes research across several areas of multi-agent systems, focusing in particular on aspects related to resilience, reliability, and coordination. In this article we introduce the group and highlight past research successes in those themes, building a picture of the strengths within the group. We close the paper outlining the future direction of the group and identify key open challenges and our vision towards solving them.
Collapse
Affiliation(s)
- Rafael C. Cardoso
- Department of Computing Science, University of Aberdeen, Aberdeen AB24 3UE, UK
| | - Brian Logan
- Department of Computing Science, University of Aberdeen, Aberdeen AB24 3UE, UK
| | - Felipe Meneguzzi
- Department of Computing Science, University of Aberdeen, Aberdeen AB24 3UE, UK
| | - Nir Oren
- Department of Computing Science, University of Aberdeen, Aberdeen AB24 3UE, UK
| | - Bruno Yun
- Department of Computing Science, University of Aberdeen, Aberdeen AB24 3UE, UK
| |
Collapse
|
6
|
Rabkina I, Kantharaju P, Wilson JR, Roberts M, Hiatt LM. Evaluation of Goal Recognition Systems on Unreliable Data and Uninspectable Agents. Front Artif Intell 2022; 4:734521. [PMID: 35187473 PMCID: PMC8849203 DOI: 10.3389/frai.2021.734521] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 07/01/2021] [Accepted: 12/24/2021] [Indexed: 11/23/2022] Open
Abstract
Goal or intent recognition, where one agent recognizes the goals or intentions of another, can be a powerful tool for effective teamwork and improving interaction between agents. Such reasoning can be challenging to perform, however, because observations of an agent can be unreliable and, often, an agent does not have access to the reasoning processes and mental models of the other agent. Despite this difficulty, recent work has made great strides in addressing these challenges. In particular, two Artificial Intelligence (AI)-based approaches to goal recognition have recently been shown to perform well: goal recognition as planning, which reduces a goal recognition problem to the problem of plan generation; and Combinatory Categorical Grammars (CCGs), which treat goal recognition as a parsing problem. Additionally, new advances in cognitive science with respect to Theory of Mind reasoning have yielded an approach to goal recognition that leverages analogy in its decision making. However, there is still much unknown about the potential and limitations of these approaches, especially with respect to one another. Here, we present an extension of the analogical approach to a novel algorithm, Refinement via Analogy for Goal Reasoning (RAGeR). We compare RAGeR to two state-of-the-art approaches which use planning and CCGs for goal recognition, respectively, along two different axes: reliability of observations and inspectability of the other agent's mental model. Overall, we show that no approach dominates across all cases and discuss the relative strengths and weaknesses of these approaches. Scientists interested in goal recognition problems can use this knowledge as a guide to select the correct starting point for their specific domains and tasks.
Collapse
Affiliation(s)
- Irina Rabkina
- Computer Science Department, Occidental College, Los Angeles, CA, United States
- *Correspondence: Irina Rabkina
| | - Pavan Kantharaju
- Smart Information Flow Technologies, Minneapolis, MN, United States
| | - Jason R. Wilson
- Computer Science Department, Franklin & Marshall College, Lancaster, PA, United States
| | - Mark Roberts
- The U.S. Naval Research Laboratory, Washington, DC, United States
| | - Laura M. Hiatt
- The U.S. Naval Research Laboratory, Washington, DC, United States
| |
Collapse
|
7
|
Masters P, Smith W, Kirley M. Extended Goal Recognition: Lessons from Magic. Front Artif Intell 2021; 4:730990. [PMID: 34870184 PMCID: PMC8633958 DOI: 10.3389/frai.2021.730990] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Grants] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 06/25/2021] [Accepted: 09/27/2021] [Indexed: 11/13/2022] Open
Abstract
The "science of magic" has lately emerged as a new field of study, providing valuable insights into the nature of human perception and cognition. While most of us think of magic as being all about deception and perceptual "tricks", the craft-as documented by psychologists and professional magicians-provides a rare practical demonstration and understanding of goal recognition. For the purposes of human-aware planning, goal recognition involves predicting what a human observer is most likely to understand from a sequence of actions. Magicians perform sequences of actions with keen awareness of what an audience will understand from them and-in order to subvert it-the ability to predict precisely what an observer's expectation is most likely to be. Magicians can do this without needing to know any personal details about their audience and without making any significant modification to their routine from one performance to the next. That is, the actions they perform are reliably interpreted by any human observer in such a way that particular (albeit erroneous) goals are predicted every time. This is achievable because people's perception, cognition and sense-making are predictably fallible. Moreover, in the context of magic, the principles underlying human fallibility are not only well-articulated but empirically proven. In recent work we demonstrated how aspects of human cognition could be incorporated into a standard model of goal recognition, showing that-even though phenomena may be "fully observable" in that nothing prevents them from being observed-not all are noticed, not all are encoded or remembered, and few are remembered indefinitely. In the current article, we revisit those findings from a different angle. We first explore established principles from the science of magic, then recontextualise and build on our model of extended goal recognition in the context of those principles. While our extensions relate primarily to observations, this work extends and explains the definitions, showing how incidental (and apparently incidental) behaviours may significantly influence human memory and belief. We conclude by discussing additional ways in which magic can inform models of goal recognition and the light that this sheds on the persistence of conspiracy theories in the face of compelling contradictory evidence.
Collapse
Affiliation(s)
- Peta Masters
- School of Computing and Information Systems, The University of Melbourne, Melbourne, VIC, Australia
| | | | | |
Collapse
|
8
|
|
9
|
Van-Horenbeke FA, Peer A. Activity, Plan, and Goal Recognition: A Review. Front Robot AI 2021; 8:643010. [PMID: 34041274 PMCID: PMC8141730 DOI: 10.3389/frobt.2021.643010] [Citation(s) in RCA: 6] [Impact Index Per Article: 2.0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 12/17/2020] [Accepted: 04/06/2021] [Indexed: 01/08/2023] Open
Abstract
Recognizing the actions, plans, and goals of a person in an unconstrained environment is a key feature that future robotic systems will need in order to achieve a natural human-machine interaction. Indeed, we humans are constantly understanding and predicting the actions and goals of others, which allows us to interact in intuitive and safe ways. While action and plan recognition are tasks that humans perform naturally and with little effort, they are still an unresolved problem from the point of view of artificial intelligence. The immense variety of possible actions and plans that may be encountered in an unconstrained environment makes current approaches be far from human-like performance. In addition, while very different types of algorithms have been proposed to tackle the problem of activity, plan, and goal (intention) recognition, these tend to focus in only one part of the problem (e.g., action recognition), and techniques that address the problem as a whole have been not so thoroughly explored. This review is meant to provide a general view of the problem of activity, plan, and goal recognition as a whole. It presents a description of the problem, both from the human perspective and from the computational perspective, and proposes a classification of the main types of approaches that have been proposed to address it (logic-based, classical machine learning, deep learning, and brain-inspired), together with a description and comparison of the classes. This general view of the problem can help on the identification of research gaps, and may also provide inspiration for the development of new approaches that address the problem in a unified way.
Collapse
Affiliation(s)
- Franz A Van-Horenbeke
- Human-Centered Technologies and Machine Intelligence Lab, Faculty of Science and Technology, Free University of Bozen-Bolzano, Bolzano, Italy
| | - Angelika Peer
- Human-Centered Technologies and Machine Intelligence Lab, Faculty of Science and Technology, Free University of Bozen-Bolzano, Bolzano, Italy
| |
Collapse
|