Local search techniques for multi-agent constraint optimization problems
Combinatorial optimization problems in the real world are ubiquitous. Practical applications include planning, scheduling, distributed control, resource allocation, etc. These problems often involve multiple agents and can be formulated as a Multi-agent Constraint Optimization Problem (MCOP). A major challenge in such systems is the agent coordination, such that a global optimal outcome is achieved. This thesis is devoted to two major issues that arise in MCOP: efficient optimization algorithms and manipulations from self-interested agents. We introduce a new randomized local search optimization algorithm called Random Subset Optimization (RSO). The RSO algorithm is tested on various applications and demonstrated to converge faster than other local search techniques while achieving competitive performance. For self-interested agents, we define a new form of incentive compatibility called size-limited incentive compatibility and show that RSO algorithm can be used to prevent agents' manipulations.
Keywords: artificial intelligence ; constraint optimization ; local search ; incentive-compatibility ; mechanism design ; intelligence artificielle ; optimisation sous contraintes ; recherche locale ; incentive-compatibility ; mechanism designThèse École polytechnique fédérale de Lausanne EPFL, n° 4074 (2008)
Programme doctoral Informatique, Communications et Information
Faculté informatique et communications
Institut d'informatique fondamentale
Laboratoire d'intelligence artificielle
Record created on 2008-03-20, modified on 2016-08-08