Yang Xu

Project

The Cooperative Attack Munition Real Time Assessment (CAMRA) project is a joint project between the Intelligent Software Agents Lab in the Robotics Institute and University of Pittsburgh to develop large teams of autonomous Wide Area Search Munitions (WASMs) that can be controlled by a small number of human operators. A WASM is a cross between a unmanned aerial vehicle - it can sense its environment and react to changing situations - and a smart bomb - it can destroy targets by hitting them. The Air Force sponsors of the project envision having hundreds or even thousands of WASMs flying in support of troops within a hostile battle space. Achieving this vision requires overcoming some significant technical challenges. CMU's role in this project is to develop the algorithms required to achieve cohesive, flexible and robust coordination in the hostile environment.
A number of intertwined algorithms are required for effective coordination. One algorithm needs to initiate, monitor and terminate joint plans. Another algorithm needs to determine which information should be communicated from one group member to another, based on the costs, benefits and risks of that communication. Another key algorithm, especially in dynamic environments, allocates roles to group members to best leverage the abilities of the group members towards the joint goal. Additional algorithms are required to manage access to shared resources or form sub-groups or create plans. Notice, that all the coordination algorithms are distributed and must operate despite a noisy, dynamic environment. While algorithms for each of these problems exist, they typically do not scale up to the size of the group that we need to coordinate in the CAMRA project. Thus, we are actively developing and extending these critical algorithms to ensure they are appropriate for very large teams.
To ensure the generality of our work we are encapsulating the generic coordination algorithms in domain independent "proxies" that operate in close cooperation with domain dependent "control agents". These proxies are lightweight Java processes that have been specifically designed to meet the challenges of large scale, highly heterogeneous teams. Two key areas where these proxies depart dramatically from previous efforts are in the role allocation mechanism and communication reasoning. The role allocation algorithm is a highly scalable algorithm based on ideas from distributed constraint optimization. The key is to represent roles as tokens and allow only the proxy currently holding a token to assume that role. Using probabilistic information about the overall situation, each proxy decides whether to accept the role represented by the token or pass it on. By intelligently passing and holding tokens, the group can rapidly find good allocations and robustly adapt the allocations when the situation changes. Second, we are developing novel algorithms for communication reasoning that do not rely on the accurate models of group members typically relied on in previous work.
Webpage

Professional Activities

Program Committee: 3rd workshop on challenges in the coordination of large scale multi-agent systems, AAMAS2006

Publications

Yang Xu, Paul Scerri, Katia Sycara, and Michael Lewis, Comparing Market and Token-Based Coordination, AAMAS, 2006, To appear

Bin Yu, Paul Scerri, Katia Sycara, Yang Xu, and Michael Lewis, Scalable and Reliable Data Delivery in Mobile Ad Hoc Sensor Networks, AAMAS, 2006, To appear

Paul Scerri, Bin Yu, Yang Xu, Katia Sycara, A Decentralized Approach to Cooperative Path Planning for Large Teams, AAMAS, 2006, To appear

Yang Xu, Paul Scerri, Bin Yu, Steven Okamoto, Katia Sycara, and Michael Lewis, An Integrated Token-Based Algorithm for Scalable Coordination, AAMAS, 2005, (finalist for best paper award, 24% acceptance rate)

Yang Xu, Paul Scerri, Bin Yu, Michael Lewis, and Katia Sycara, A POMDP Approach to Token-Based Team Coordination, AAMAS Workshop on Challenges in the Coordination of Large Scale Multiagent Systems, 2005, to appear

Y. Xu, E. Liao, P. Scerri, B. Yu, K. Sycara and M. Lewis "Towards Flexible Coordination of Large Scale MultiAgent Teams", In Challenges of Large Scale Coordination, Springer, 2005
P. Scerri, Y. Xu, J. Polvichai, B. Yu, S. Okamoto, M. Lewis and K. Sycara, "Challenges in Building Very Large Teams", In Cooperative Control (name subject to change), forthcoming.
Scerri, P., Xu, Yang., Liao, E., Lai, J. and Sycara, K. "Scaling Teamwork to Very Large Teams" , In AAMAS'04, 2004.
Xu, Y., Lewis, M., Sycara, K. and Scerri, P. "Information Sharing in Large Scale Teams" , In AAMAS'04 Workshop on Challenges in Coordination of Large Scale MultiAgent Systems, 2004.

Scerri, P., Liao, E., Xu, Yang., Lewis, M., Lai, G. and Sycara, K. "Coordinating very large groups of wide area search munitions" , In Theory and Algorithms for Cooperative Systems, World Scientific Publishing.

Joseph Giampapa, Katia Sycara, Sean Owens, Robin Glinton, Young-Woo Seo, Bin Yu, Charles E. Grindle, Yang Xu, Michael Lewis An Agent-Based C4ISR Testbed, Proceedings of Eighth International Conference on Information Fusion (FUSION), 2005, to appear

A Study of Agent-Based Distributed Hierarchical Intelligent Control. Control and Decision (2001, Vol.2 No.1001-0920(2001)02-0177-04)

A Study and It's application of Agent-Based Distributed Hierarchical Intelligent. Automation and Instrumentation (2001, Vol.3 No.1001-9944(2001)03-0026-04)

An Architecture of Agent-Based Intelligent Control System. Proceedings of the 3rd World Congress on Intelligent Control and Automation

A Method Study Based on Constraint Satisfaction for Intelligent Composing Test Paper. Application Research of Computers (2001, vol.11 No.1001-3695(2000)11-0020-03)