AIC Seminar Series

Cooperative mediation is a powerful new method for solving distributed problems. Cooperative mediation works by having each agent dynamically and incrementally centralize relevant portions of a shared problem in order to rapidly converge on a globally acceptable solution. This technique is effective because it uses the structure of the problem and current solution state to focus computation while simultaneously exploiting the speed of centralized algorithms. Philosophically, this work represents a change in focus in distributed problem solving because, unlike techniques that attempt to maintain complete distribution of knowledge and control, this technique capitalizes on the observation that some centralization is always necessary. In this talk, I will describe the scalable, periodic, anytime mediation protocol which was created for solving real-time, distributed resource allocation problems in a real-world sensor network. I will show how the key ideas from this protocol lead to the inception of the cooperative mediation paradigm and subsequently to the creation of an entire family of algorithms for solving a variety of distributed problems. Most notably among these algorithms are asynchronous partial overlay (APO) for solving distributed constraint satisfaction problems and optimal asynchronous partial overlay (OptAPO) for solving distributed constraint optimization problems. These algorithms have been extensively analyzed and tested and shown to be superior to the previously best-known algorithms for solving these problems. I will conclude my talk by showing an application of the APO algorithm to the problem of distributed airspace deconfliction. Additional applications of cooperative mediation include supply chain and work-flow management and distributed scheduling and resource allocation.

Roger Mailler received a PhD from the University of Massachusetts in May 2004 and a B.S. with Honors in computer science from the State University of New York at Stony Brook in 1999. He currently works as a Postdoctoral associate at the Intelligent Information Systems Institute (IISI) at Cornell University where he acts as the liaison to the Air Force Research Lab (AFRL) in Rome, NY. His main research interests are multi-agent systems, distributed constraint satisfaction and optimization, distributed sensor networks, and machine learning.

Please arrive at least 10 minutes early in order to sign in and be escorted to the conference room. SRI is located at 333 Ravenswood Avenue in Menlo Park. Visitors may park in the visitors lot in front of Building E, and should follow the instructions by the lobby phone to be escorted to the meeting room. Detailed directions to SRI, as well as maps, are available from the Visiting AIC web page.

©2013 SRI International 333 Ravenswood Avenue, Menlo Park, CA 94025-3493
SRI International is an independent, nonprofit corporation. Privacy policy