HMPCC: Human-Aware Model Predictive Coverage Control

1. Problem Statement

The paper addresses the challenge of coordinating a team of robots to cover an unknown, potentially non-convex environment while ensuring safe operation alongside non-cooperative, unpredictable human agents.

Traditional coverage control methods (e.g., Voronoi tessellation, Lloyd's algorithm) typically suffer from three major limitations in real-world scenarios:

1. Simplified Assumptions: They often assume convex environments and known density functions.
2. Static Dynamics: They frequently rely on simple single-integrator dynamics, failing to account for complex robot kinematics (e.g., unicycle or double integrator models).
3. Reactive Human Handling: They treat humans as static obstacles or reactive entities, lacking the ability to anticipate human motion, which leads to inefficiency or collisions in dynamic, shared spaces.

The core objective is to develop a decentralized control framework that allows robots to optimize coverage, respect complex dynamics, avoid obstacles, and safely navigate around humans without relying on explicit inter-robot communication.

2. Methodology: HMPCC Framework

The authors propose HMPCC (Human-Aware Model Predictive Coverage Control), a framework that integrates Model Predictive Control (MPC) with Human Trajectory Prediction (HTP).

A. Environment and Robot Modeling

• Environment: Modeled as a 2D polygon $Q$ containing obstacles and a Gaussian Mixture Model (GMM) representing the likelihood density $\phi(q)$ of areas of interest.
• Robot Dynamics: The framework supports generic non-linear dynamics described by $\dot{x}_i = f(x_i) + g(x_i)u_i$, accommodating various robot types (e.g., unicycle, double integrator).
• Decentralization: Robots operate independently using only local sensing (limited range $R$) and neighbor information, with no explicit communication required.

B. Human Trajectory Prediction (HTP)

To handle human unpredictability, the system employs a probabilistic predictor.

• Prediction Model: At time $t_0$, the future position of the $i$-th human at step $k$ is modeled as a Gaussian distribution: $\xi_i(t_0+k|t_0) \sim \mathcal{N}(\mu^k_i, \Sigma^k_i)$.
• Uncertainty Handling: The covariance matrix $\Sigma^k_i$ grows over the prediction horizon to reflect increasing uncertainty in human motion.

C. The MPC Optimization Problem

The core of HMPCC is a Quadratic Programming (QP) problem solved at each time step to generate a sequence of control inputs $U_i$. The objective is to minimize a cost function $J_i$ subject to safety and dynamic constraints.

1. Cost Function ($J_i$):
$$J_i = J^{cov}_i + J^u_i + J^\delta_i$$

• Coverage Cost ($J^{cov}_i$): Minimizes the distance between robots and the centroids of their limited-range Voronoi cells, weighted by the density function $\phi(q)$. Unlike traditional methods, this is integrated over a fixed initial Voronoi cell to maintain convexity in the optimization.
• Control Effort ($J^u_i$): Penalizes aggressive maneuvers ($u_i^T R u_i$) to ensure smooth trajectories.
• Relaxation Cost ($J^\delta_i$): A penalty term for slack variables used to relax human avoidance constraints at the end of the horizon, balancing safety with coverage goals.

2. Constraints:

• Dynamics: Discretized robot motion equations must be satisfied.
• Obstacle Avoidance: Hard constraints ensuring a minimum safety distance $D_s$ from static obstacles.
• Human Avoidance (Chance Constraints): Instead of hard constraints, the system uses chance constraints to handle probabilistic human motion:
  $$P(\|\xi_j - p_i\| < D_s) \leq \alpha$$
  This is transformed into a constraint on the Mahalanobis distance ($d_M$) between the robot and the predicted human distribution. A slack variable $\delta_k$ allows the constraint to become less conservative as the prediction horizon extends, preventing the system from becoming overly conservative and stuck.

3. Key Contributions

1. Generalized MPC Framework: An optimization-based coverage controller that handles non-convex environments and generic robot dynamics (beyond simple single integrators), overcoming the limitations of traditional Voronoi-based methods.
2. Proactive Human-Awareness: The integration of Human Trajectory Prediction directly into the MPC formulation. By anticipating human paths via chance constraints, robots can proactively adjust their trajectories to avoid collisions rather than reacting to them.
3. Decentralized Operation: The system functions without inter-agent communication, making it suitable for hostile or communication-denied scenarios.
4. Probabilistic Safety: The use of chance constraints with slack variables provides a mathematically rigorous way to balance safety (collision avoidance) and performance (coverage efficiency) in the presence of uncertainty.

4. Experimental Results

The authors evaluated HMPCC against a baseline hybrid approach (Limited-range Voronoi + Potential-based repulsion) in three scenarios:

• Convex Environment (No Humans):
  • HMPCC demonstrated faster convergence to the optimal coverage configuration compared to the baseline. The optimization-based approach allowed robots to move more efficiently toward high-density regions.
• Non-Convex Environment (No Humans):
  • The baseline controller frequently got trapped in local minima when obstacles blocked direct paths to centroids.
  • HMPCC successfully navigated around obstacles to reach target areas, achieving superior coverage effectiveness ($E$) and objective function values ($H$).
• Non-Convex Environment (With Humans):
  • Success Rate: HMPCC achieved a 100% success rate (no collisions) across various human counts (3, 6, 9), whereas the baseline failed significantly (success rates dropped to 20-60%) due to collisions.
  • Behavior: Robots successfully predicted human paths, temporarily dispersing to make room for approaching humans, and then returning to coverage tasks.
  • Metrics: Despite temporary deviations to avoid humans, HMPCC maintained high coverage effectiveness ($E \approx 0.95$ with 3 humans).

Physical Simulation: The method was validated in Gazebo with TurtleBot3 robots, confirming computational feasibility at a 10 Hz control frequency on standard hardware.

5. Significance and Conclusion

This work represents a significant step forward in multi-robot systems operating in human-centric environments.

• Safety & Efficiency: It proves that integrating human motion prediction into the planning loop is superior to reactive collision avoidance, leading to safer and more efficient coverage.
• Robustness: By encoding dynamics and constraints directly into the optimization, the system is robust to complex environments and diverse robot types.
• Practicality: The decentralized nature and lack of communication requirements make the approach viable for real-world applications such as search and rescue, surveillance, and environmental monitoring in crowded or hostile settings.

Future work aims to incorporate more advanced prediction models (e.g., FlowChain) and validate the system in real-world physical experiments.