Optimisation

Multi-agent systems applications in a number of areas such as e-commerce, disaster management, and information acquisition through embedded devices (e.g. wireless sensor networks) have generated a number of new challenges for algorithm designers. These challenges mainly take the form of very hard optimisation problems that are substantially different from problems traditionally dealt with in other areas (e.g. industrial processes or scheduling applications). More specifically, novel challenges come from the distributed nature of multiagent systems where the actors reside on different computational units and can communicate only a limited amount of information with their neighbours. Moreover, the agents may be acting on behalf of different stakeholders each with its own aims and objectives, have different computation/communication capabilities, and be tied to physical devices prone to failures. Moreover, given the dynamic nature of the application scenarios, effective algorithms have to provide anytime solutions and approximate techniques are often required/desirable.

We focus on the design of techniques for coordinating large populations of agents by modelling the coordination problem as a distributed constraint optimisation problem (DCOP). In particular, we mainly focus on:

• the design of complete algorithms
• the design of approximate algorithms that provide anytime solutions
• assessing quality guarantees both prior to the execution of an algorithm (at design time) and during the execution of an algorithm (run time)