AIC Seminar Series

Optimizing over a set of alternatives that have varying degrees of global quality is a fundamental problem in multiagent systems. A key outstanding challenge is performing optimization in a decentralized manner. In this talk, we formulate this problem as a Distributed Constraint Optimization Problem (DCOP). Existing methods for DCOP that guarantee optimality are prohibitively slow, while other incomplete methods may provide solutions of arbitrarily poor quality in the worst case. To overcome these limitations, we present a new lower-bound based method for DCOP, named Adopt, which uses asynchronous communication to find either the global optimal solution or an approximate solution within a user-specified distance from the optimal. When finding the optimal solution, Adopt's asynchrony provides speedups of several orders of magnitude over existing complete methods. When finding approximate solutions, Adopt's lower-bound search method is able to provide a theoretical bound on worst-case solution quality. Finally, we discuss how Adopt obtains these desirable properties via a novel Instant-Conservative Communication Principle, which we conjecture has potential application to many other distributed optimization problems.

Pragnesh Jay Modi received his B.S. with University Honors in Computer Science and Mathematics in 1997 from Carnegie-Mellon University. Over past five years, he has been a graduate research assistant at the University of Southern California's Information Sciences Institute. He is expected to defend his dissertation titled "Distributed Constraint Optimization and its Application to Multiagent Systems" in Spring 2003.

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