Feasible Region-based Identification Using Duality (Extended Version)

Jaskaran Grover, Changliu Liu, Katia P. SycaraarXiv 2020 · arXiv

Abstract

In multi-robot systems, standard algorithms often fail to identify a robot's underlying task because frequent collision avoidance maneuvers "mask" its true intentions. This paper introduces a novel feasible region-based identification method that uses optimization duality to calculate a shrinking set of possible parameters rather than a single (often incorrect) point estimate. By leveraging Karush-Kuhn-Tucker (KKT) conditions, the approach provides an "anytime" estimate that converges to the true task parameters much faster than traditional filters like the Unscented Kalman Filter (UKF).

Introduction: The Challenge of Task Inference

Identifying the goals of autonomous agents is a fundamental problem in multi-robot observation. Standard tools, such as the Unscented Kalman Filter (UKF), rely on the "persistency of excitation" condition—the requirement that an agent's motion clearly reveals its underlying parameters. However, in real-world scenarios, robots frequently prioritize safety, swerving to avoid collisions. These interactions violate the persistency condition, causing standard estimators to become "confused" or stop updating as safety constraints dominate the observed motion. This paper addresses the challenge of inferring tasks in "closed-loop" scenarios where the observer cannot intervene and robots prioritize safety over task transparency.

Methods: From Points to Regions

The proposed method shifts the paradigm from point-wise estimation (guessing a single coordinate) to region-based identification (defining a polytope where the goal must reside).

  1. Optimization-Based Control: The framework assumes robots utilize Control Barrier Function-based Quadratic Programs (CBF-QPs) to balance goal-seeking with safety guarantees.
  2. KKT Conditions & Duality: By analyzing the KKT conditions of the robot's internal optimization problem, the authors derive explicit relationships between observed velocity, safety constraints, and hidden task parameters.
  3. SVD Analysis: Singular Value Decomposition (SVD) is employed to classify interaction scenarios based on the rank of the active constraint matrix.
  4. Set Intersection: At each time step, an "instantaneous feasible set" $\Omega(t)$ is calculated. By intersecting these sets over time, the observer maintains a "cumulative feasible region" $\Theta(t)$ that is guaranteed to contain the true parameter and strictly non-increases in size.

Key Results and Insights

The region-based approach treats collision avoidance maneuvers as informative data rather than noise. Knowing what a robot is avoiding helps narrow down what it is pursuing.

Comparison of identification feasibility across different constraint scenarios.

As illustrated in the table above, the paper identifies specific scenarios (Cases D and E) where point-wise estimation is mathematically impossible because the robot's dynamics become independent of its task parameters during complex maneuvers. In these instances, the region-based method remains effective, providing a clear advantage in robustness.

Simulations demonstrate that the area of the feasible region shrinks to the true parameter significantly faster than the error of a UKF converges to zero. Furthermore, the method provides "anytime validity": every point inside the feasible region is a mathematically valid candidate at any moment, preventing the "wandering" estimates often seen in filters during periods of low excitation.

Conclusion and Future Work

While the method shows great promise, it currently requires knowledge of the mathematical form of the robot's controller. Future work aims to address computational complexity in high-dimensional spaces and explore "active sensing," where an observer might move to force robots to reveal their tasks more quickly. The authors also intend to deepen the theoretical links between this duality-based approach and broader inverse convex optimization.

Summary updated

Abstract

We consider the problem of estimating bounds on parameters representing tasks being performed by individual robots in a multirobot system. In our previous work, we derived necessary conditions based on persistency of excitation analysis for the exact identification of these parameters. We concluded that depending on the robot's task, the dynamics of individual robots may fail to satisfy these conditions, thereby preventing exact inference. As an extension to that work, this paper focuses on estimating bounds on task parameters when such conditions are not satisfied. Each robot in the team uses optimization-based controllers for mediating between task satisfaction and collision avoidance. We use KKT conditions of this optimization and SVD of active collision avoidance constraints to derive explicit relations between Lagrange multipliers, robot dynamics, and task parameters. Using these relations, we are able to derive bounds on each robot's task parameters. Through numerical simulations, we show how our proposed region based identification approach generates feasible regions for parameters when a conventional estimator such as a UKF fails. Additionally, empirical evidence shows that this approach generates contracting sets which converge to the true parameters much faster than the rate at which a UKF based estimate converges. Videos of these results are available at https://bit.ly/2JDMgeJ
BibTeX
@misc{grover2020feasible,
  author = {Jaskaran Grover and Changliu Liu and Katia P. Sycara},
  title = {{Feasible Region-based Identification Using Duality (Extended Version)}},
  year = {2020},
  eprint = {2011.04904},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2011.04904},
}
Figure