Parameter Identification for Multirobot Systems Using Optimization-based Controllers

Jaskaran Grover, Changliu Liu, Katia P. Sycara

TL;DR

This paper tackles the challenge of an adversary identifying a multirobot system's task parameters (like goals and controller gains) by only observing robot positions. They develop a novel framework using optimization theory and SVD to derive necessary conditions for successful identification, showing that more complex interactions make identification harder. Simulations confirm that these conditions accurately predict when standard estimation algorithms succeed or fail.

What Problem Does This Paper Address?

Imagine a team of robots performing tasks, like navigating to specific locations while avoiding each other. Now, imagine an adversary who can only see where these robots are. Can the adversary figure out what the robots are trying to achieve (their goals) or how they are programmed (their controller parameters)? This is the core problem: parameter identification for multirobot systems, specifically when robots use complex optimization-based controllers for tasks like collision avoidance.

The difficulty arises because these optimization controllers don't have a simple, explicit mathematical formula linking the task parameters (e.g., goal position $x_d$, gain $k_p$) to the robot's movement ($u$). Instead, the relationship is implicit, making it hard to apply standard system identification techniques that require explicit dynamics. The paper aims to bridge this gap by finding out when an adversary can reliably infer these parameters and when they are fundamentally unable to.

Methods

The authors leverage concepts from system identification, particularly persistency of excitation (PE), which essentially means the system's inputs and states need to be sufficiently "rich" or varied over time for accurate parameter estimation. To overcome the implicit nature of optimization-based control, they employ:

  • Duality Theory and KKT Conditions: They analyze the Karush-Kuhn-Tucker (KKT) conditions of the robot's optimization problem. This allows them to derive an explicit relationship between the robot's control input ($u$) and the task parameters ($x_d, k_p$), even though the original controller is implicit.
  • Singular Value Decomposition (SVD): By analyzing the SVD of the active collision avoidance constraints, they can further refine the relationship between control and parameters. This is crucial for understanding how the number and dependency of these constraints affect identifiability.
  • Classification of Dynamics: They categorize the robot's dynamics based on the number of active collision avoidance constraints and their linear independence. This leads to different identifiability conditions for different scenarios (no active constraints, one active constraint, multiple linearly dependent constraints, multiple linearly independent constraints).
  • Adaptive Observer (AO): They propose an adaptive observer based on established parameter estimation techniques, tailored to the derived explicit dynamics.
  • Unscented Kalman Filter (UKF): They use a UKF as a baseline to compare their AO's performance, as UKFs are generally robust to model uncertainties.

Datasets

Not discussed in the paper. The evaluation is performed using simulated scenarios with varying numbers and configurations of static obstacles.

Key Insights and Ideas

  • The "Curse of Interaction": The most significant insight is that as an ego robot interacts with more active obstacles (i.e., obstacles it needs to actively avoid), its control effort is increasingly consumed by collision avoidance. This leaves less "room" for the control to reflect the task parameters (goal, gain), making identification progressively harder.
  • Implicit vs. Explicit Dynamics: The core technical contribution is deriving an explicit relationship between task parameters and robot dynamics from an implicit optimization-based controller. This is achieved by carefully analyzing the KKT conditions and the structure of active constraints.
  • Identifiability is Geometric: The conditions for successful parameter identification are directly tied to the geometric configuration of the robots and obstacles. Specifically, the number of active constraints and their linear dependency play a critical role.
  • Null Space Matters: The null space of the constraint matrix is key. If this null space is time-invariant, it implies a pathological parameter that doesn't affect the observed dynamics, rendering identification impossible.
  • Observer Performance Mirrors Theory: The simulations beautifully demonstrate that the proposed adaptive observer (and even the UKF) performs as predicted by the theoretical conditions. When identification is theoretically feasible, the estimators converge; when it's not, they fail.

Key Results

The paper establishes necessary conditions for parameter identification based on the number and nature of active collision avoidance constraints:

  • No Active Constraints (Theorem 2): Identification of goal and gain is always possible.
  • Exactly One Active Constraint (Theorem 3): Identification is possible as long as the orientation of the constraint is not time-invariant and the robot is not at its goal.
  • Multiple Linearly Dependent Active Constraints (Theorem 5): Similar to the single active constraint case, identification is possible if the orientation of the "representative" constraint is not time-invariant.
  • Two or More Linearly Independent Active Constraints (Theorem 6): Identification of goal or gain is impossible. In this scenario, the robot's control is fully determined by the collision avoidance constraints, and it "gives up" on optimizing the task objective.

Simulations using an Adaptive Observer and UKF validate these theorems. They show convergence of estimation errors when conditions are met and stagnation or divergence when they are not.

Limitations and Future Work

  • Focus on Specific Controller: The analysis is based on a specific type of optimization-based controller (CBF-QP for goal stabilization and collision avoidance). While the framework is generalizable, specific derivations might change for other controllers.
  • Static Obstacles in Simulations: The simulations primarily use static obstacles. Future work could explore dynamic obstacles.
  • Decoupled Identification: The analysis focuses on identifying goal and gain separately for simplicity. Joint identification is mentioned as a straightforward extension.
  • Future Work:
    • Demonstrate the framework for other multirobot tasks.
  • Apply the theory to infer parameters of human tasks and explore how robots can intervene to make human task identification easier.
  • Explore applications in human-robot interaction.

Summary updated

Abstract

This paper considers the problem of parameter identification for a multirobot system. We wish to understand how can an adversarial observer reverse-engineer the tasks being performed by a team of robots by simply observing their positions. To address this question, we use the concept of persistency of excitation from system identification. Each robot in the team uses optimization-based controllers for mediating between task satisfaction and collision avoidance. These controllers exhibit an implicit dependence on the task's parameters which poses a hurdle for deriving necessary conditions for parameter identification, since such conditions usually require an explicit relation. We address this bottleneck by using duality theory and SVD of active collision avoidance constraints and derive an explicit relation between each robot's task parameters and its control inputs. This allows us to derive the main necessary conditions for successful identification which agree with our intuition. We demonstrate the importance of these conditions through numerical simulations by using (a) an adaptive observer and (b) an unscented Kalman filter for goal and gain estimation in various geometric settings. These simulations show that under circumstances where parameter inference is supposed to be infeasible per our conditions, both these estimators fail, and likewise when it is feasible, both converge to the true parameters. Videos of these results are available at https://tinyurl.com/6v6bmk86
BibTeX
@inproceedings{grover2021parameter,
  author = {Jaskaran Grover and Changliu Liu and Katia P. Sycara},
  title = {{Parameter Identification for Multirobot Systems Using Optimization-based Controllers}},
  booktitle = {MRS},
  year = {2021},
  url = {https://openreview.net/forum?id=4-Dk9pJdNZ},
}
Figure