Goal Recognition via Linear Programming

• URL: http://arxiv.org/abs/2404.07934v1
• Date: Thu, 11 Apr 2024 17:34:35 GMT
• Title: Goal Recognition via Linear Programming
• Authors: Felipe Meneguzzi, Luísa R. de A. Santos, Ramon Fraga Pereira, André G. Pereira,
• Abstract summary: Research on Goal Recognition as Planning encompasses reasoning about the model of a planning task, the observations, and the goals using planning techniques. In this article, we design novel recognition approaches that rely on the Operator-Counting framework. We show how the new IP/LP constraints can improve the recognition of goals under both partial and noisy observability.
• Score: 14.129476759815251
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Goal Recognition is the task by which an observer aims to discern the goals that correspond to plans that comply with the perceived behavior of subject agents given as a sequence of observations. Research on Goal Recognition as Planning encompasses reasoning about the model of a planning task, the observations, and the goals using planning techniques, resulting in very efficient recognition approaches. In this article, we design novel recognition approaches that rely on the Operator-Counting framework, proposing new constraints, and analyze their constraints' properties both theoretically and empirically. The Operator-Counting framework is a technique that efficiently computes heuristic estimates of cost-to-goal using Integer/Linear Programming (IP/LP). In the realm of theory, we prove that the new constraints provide lower bounds on the cost of plans that comply with observations. We also provide an extensive empirical evaluation to assess how the new constraints improve the quality of the solution, and we found that they are especially informed in deciding which goals are unlikely to be part of the solution. Our novel recognition approaches have two pivotal advantages: first, they employ new IP/LP constraints for efficiently recognizing goals; second, we show how the new IP/LP constraints can improve the recognition of goals under both partial and noisy observability.

Related papers

• Directed Exploration in Reinforcement Learning from Linear Temporal Logic [59.707408697394534]
  Linear temporal logic (LTL) is a powerful language for task specification in reinforcement learning. We show that the synthesized reward signal remains fundamentally sparse, making exploration challenging. We show how better exploration can be achieved by further leveraging the specification and casting its corresponding Limit Deterministic B"uchi Automaton (LDBA) as a Markov reward process.
  arXiv  Detail & Related papers  (2024-08-18T14:25:44Z)
• Expectation Alignment: Handling Reward Misspecification in the Presence of Expectation Mismatch [19.03141646688652]
  We use the theory of mind, i.e., the human user's beliefs about the AI agent, as a basis to develop a formal explanatory framework. We propose a new interactive algorithm that uses the specified reward to infer potential user expectations.
  arXiv  Detail & Related papers  (2024-04-12T19:43:37Z)
• On efficient computation in active inference [1.1470070927586016]
  We present a novel planning algorithm for finite temporal horizons with drastically lower computational complexity. We also simplify the process of setting an appropriate target distribution for new and existing active inference planning schemes.
  arXiv  Detail & Related papers  (2023-07-02T07:38:56Z)
• Imitating Graph-Based Planning with Goal-Conditioned Policies [72.61631088613048]
  We present a self-imitation scheme which distills a subgoal-conditioned policy into the target-goal-conditioned policy. We empirically show that our method can significantly boost the sample-efficiency of the existing goal-conditioned RL methods.
  arXiv  Detail & Related papers  (2023-03-20T14:51:10Z)
• Leveraging Planning Landmarks for Hybrid Online Goal Recognition [7.690707525070737]
  We propose a hybrid method for online goal recognition that combines a symbolic planning landmark based approach and a data-driven goal recognition approach. The proposed method is significantly more efficient in terms of computation time than the state-of-the-art but also improves goal recognition performance.
  arXiv  Detail & Related papers  (2023-01-25T13:21:30Z)
• Investigating the Combination of Planning-Based and Data-Driven Methods for Goal Recognition [7.620967781722714]
  We investigate the application of two state-of-the-art, planning-based plan recognition approaches in a real-world setting. We show that such approaches have difficulties when used to recognize the goals of human subjects, because human behaviour is typically not perfectly rational. We propose an extension to the existing approaches through a classification-based method trained on observed behaviour data.
  arXiv  Detail & Related papers  (2023-01-13T15:24:02Z)
• Discrete Factorial Representations as an Abstraction for Goal Conditioned Reinforcement Learning [99.38163119531745]
  We show that applying a discretizing bottleneck can improve performance in goal-conditioned RL setups. We experimentally prove the expected return on out-of-distribution goals, while still allowing for specifying goals with expressive structure.
  arXiv  Detail & Related papers  (2022-11-01T03:31:43Z)
• C-Planning: An Automatic Curriculum for Learning Goal-Reaching Tasks [133.40619754674066]
  Goal-conditioned reinforcement learning can solve tasks in a wide range of domains, including navigation and manipulation. We propose the distant goal-reaching task by using search at training time to automatically generate intermediate states. E-step corresponds to planning an optimal sequence of waypoints using graph search, while the M-step aims to learn a goal-conditioned policy to reach those waypoints.
  arXiv  Detail & Related papers  (2021-10-22T22:05:31Z)
• Sequential Transfer in Reinforcement Learning with a Generative Model [48.40219742217783]
  We show how to reduce the sample complexity for learning new tasks by transferring knowledge from previously-solved ones. We derive PAC bounds on its sample complexity which clearly demonstrate the benefits of using this kind of prior knowledge. We empirically verify our theoretical findings in simple simulated domains.
  arXiv  Detail & Related papers  (2020-07-01T19:53:35Z)
• Reparameterized Variational Divergence Minimization for Stable Imitation [57.06909373038396]
  We study the extent to which variations in the choice of probabilistic divergence may yield more performant ILO algorithms. We contribute a re parameterization trick for adversarial imitation learning to alleviate the challenges of the promising $f$-divergence minimization framework. Empirically, we demonstrate that our design choices allow for ILO algorithms that outperform baseline approaches and more closely match expert performance in low-dimensional continuous-control tasks.
  arXiv  Detail & Related papers  (2020-06-18T19:04:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.