Search |  Contact |  SRI Home Do not follow this link, or your host will be blocked from this site. This is a spider trap. Do not follow this link, or your host will be blocked from this site. This is a spider trap. Do not follow this link, or your host will be blocked from this site. This is a spider trap.A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A ASRI International.  333 Ravenswood Avenue.  Menlo Park, CA 94025-3493. SRI International is a nonprofit corporation.

AIC Seminar Series

Constraint Optimization in Multiagent Systems

Pragnesh Jay ModiInformation Sciences Institute, USC

Date:  2003-02-27 at 16:00

Location:  EJ228  (Directions)

   Abstract

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.

   Bio for Pragnesh Jay Modi

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.

   Note for Visitors to SRI

Please arrive at least 10 minutes early as you will need to sign in by following instructions by the lobby phone at Building E. SRI is located at 333 Ravenswood Avenue in Menlo Park. Visitors may park in the parking lots off Fourth Street. Detailed directions to SRI, as well as maps, are available from the Visiting AIC web page. There are two entrances to SRI International located on Ravenswood Ave. Please check the Builing E entrance signage.

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