Experimental Demonstration of Multi-Agent Learning and Planning under Uncertainty for Persistent Missions with Automated Battery Management

Nazım Kemal Üre, Tuna Toksoz, Girish Chowdhary, Joshua Redding, Jonathan P. How, Matthew A. Vavrina, John VianAIAA 2012 · DOI

TL;DR

This paper presents an integrated learning and planning framework for multi-agent systems operating under uncertainty, specifically for persistent surveillance missions. By combining decentralized planning (Dec-MMDP/GA-Dec-MMDP) with adaptive learning (iFDD) and an automated battery management system, the authors demonstrate improved mission performance and efficiency for teams of UAVs.

What Problem Does This Paper Address?

Persistent surveillance missions, like monitoring forests or disaster areas, require autonomous systems (e.g., UAVs) to operate for extended periods. This presents several challenges:

  • Uncertainty: The health of individual agents (e.g., sensor/actuator failures) and environmental dynamics (e.g., fuel consumption) are often unknown or change during the mission. This state-correlated uncertainty makes robust planning difficult.
  • Scalability: Traditional multi-agent planning approaches become computationally intractable as the number of agents increases.
  • Endurance: UAVs have limited battery life, which restricts mission duration. Traditional recharging methods are often slow or require manual intervention.

The paper aims to address these issues by developing a system that can learn about its environment and adapt its plans in real-time, while also managing its own power resources autonomously.

Methods

The core of the proposed solution is an integrated learning-planning architecture built upon the Intelligent Cooperative Architecture (iCCA) framework. Key components include:

  • Decentralized Multi-Agent Markov Decision Processes (Dec-MMDPs) and Group Aggregate Dec-MMDPs (GA-Dec-MMDPs): These are scalable planning algorithms that allow individual agents to make decisions based on their local state and an approximation of their teammates' states. GA-Dec-MMDP further reduces complexity by aggregating teammate states.
  • Incremental Feature Discovery (iFDD): This is a compact and fast learning algorithm designed to estimate parameters of state-correlated uncertainty models. It adaptively improves its representation based on observed data, making it suitable for environments where uncertainty is not uniform.
  • Automated Battery Management System: A novel "change station" is introduced that enables time-efficient, hot-swapping of batteries for UAVs. This system also integrates charging capabilities, allowing for continuous operation and significantly extending mission duration.

The learning and planning processes are integrated in a cycle: the planner generates actions based on the current model, these actions are executed, observed data is used by the learner to update the model, and the planner then uses the updated model for the next planning cycle.

Datasets

The paper does not explicitly mention training datasets. Instead, it relies on:

  • Simulated Data: The algorithms are initially validated through simulations.
  • Flight Test Data: The core of the paper's validation comes from experimental flight tests conducted in the RAVEN test environment. This environment is equipped with a Vicon motion capture system for accurate state estimation. The authors also present data from their automated recharge station experiments.

Key Insights and Ideas

  • State-correlated uncertainty is crucial: Assuming uniform uncertainty (like constant sensor failure probability) is insufficient. The probability of events like sensor failure or fuel burn rate is highly dependent on the agent's state (location, fuel level), and accounting for this leads to significantly better performance.
  • Learning improves planning: The integrated learning-planning loop demonstrably improves mission performance over time. As the iFDD algorithm learns the state-correlated uncertainty, the planning algorithm becomes more confident and efficient, leading to lower costs.
  • Decentralization is key for scalability: While centralized planning offers optimal solutions, it's computationally infeasible for more than a few agents. Decentralized approaches like Dec-MMDP and GA-Dec-MMDP provide a practical way to scale to larger teams.
  • Automated battery management is essential for persistence: The developed hot-swapping recharge station is a critical enabler for long-duration missions, dramatically increasing vehicle utilization compared to previous methods.

Key Results

  • Performance Improvement: The integrated Dec-MMDP/GA-Dec-MMDP and iFDD framework showed significant improvements in mission performance (lower cumulative cost) as learning progressed.
  • Benchmarking: The decentralized methods (Dec-MMDP and GA-Dec-MMDP) achieved performance close to the centralized MMDP (considered the best achievable) after learning, with Dec-MMDP being 5-7% of MMDP performance and GA-Dec-MMDP being 2-3% of Dec-MMDP performance.
  • Accuracy of Learning: The iFDD algorithm was able to estimate state-correlated sensor failure probabilities with 2-3% accuracy on average in flight tests.
  • Battery Management Efficiency: The automated recharge station achieved a sustainability level of approximately 1.09 (meeting the goal of 1.05), enabling persistent missions with minimal downtime (91% vehicle utilization compared to ~10% for older methods).
  • Flight Test Validation: The integrated system was successfully demonstrated in a 3-hour persistent search and track mission with unknown state-dependent sensor failure dynamics.

Limitations and Future Work

  • Approximation Trade-offs: The decentralized formulations (Dec-MMDP and GA-Dec-MMDP) involve approximations, particularly in how agents model their teammates. This can lead to sub-optimal behavior compared to a fully centralized solution, though the paper shows this trade-off is manageable.
  • Feature Selection: While iFDD automates feature selection, the initial set of features can still influence performance and may require domain expertise.
  • Future Work: The paper suggests extending the framework to handle more complex scenarios, potentially involving more agents, dynamic environments, and a wider range of uncertainties. Further research could also explore more sophisticated state aggregation techniques for the GA-Dec-MMDP.

Summary updated

Abstract

planning problems in presence of state-correlated uncertainty.An online learning and planning framework is used to address the problem of improving planner performance for missions with state-dependent uncertain agent health dynamics. The framework includes a previously introduced Decentralized Multi-agent Markov decision process (Dec-MMDP) as an online planning algorithm that is scalable in number of agents, and Incremental Feature Discovery (iFDD) which is a compact and fast learning algorithm for estimating parameters of a state-correlated uncertainty model. In combination, this architecture yield an integrated learning-planning algorithm where the planning performance improves as uncertainty is reduced through learning. The presented algorithms are validated in a persistent search and track scenario with a novel automated battery swapping/recharging system that enables the UAVs to collaboratively track targets over durations that are signicantly larger than individual vehicle endurance with a single battery. The results indicate that the architecture can be used as an computationally ecient solution to multi-agent uncertain cooperative planning problems.
BibTeX
@inproceedings{ure2012experimental,
  author = {Nazım Kemal Üre and Tuna Toksoz and Girish Chowdhary and Joshua Redding and Jonathan P. How and Matthew A. Vavrina and John Vian},
  title = {{Experimental Demonstration of Multi-Agent Learning and Planning under Uncertainty for Persistent Missions with Automated Battery Management}},
  booktitle = {AIAA},
  year = {2012},
  doi = {10.2514/6.2012-4622},
}
Figure