Emergence of robust solutions to 0-1 optimization problems in multi-agent systems

Nature shows us in our daily life how robust, flexible and optimal self-organized modular constructions work in complex physical, chemical and biological systems, which successfully adapt to new and unexpected situations. A promising strategy is therefore to use such self-organization and pattern formation principles in engineering by designing multi-agent systems with appropriate interactions.

By extracting selection processes as one of the main principles of pattern formation, we bridge the gap between detailed knowledge of self-organization in complex systems in natural science and its constructive application in engineering. The approach is demonstrated by giving two examples: First, time-dependent robot-target assignment problems with several autonomous robots and several targets are considered as model of flexible manufacturing systems.

Each manufacturing target has to be served in a given time interval by one and only one robot and the total working costs have to be minimized (or total profits maximized). A specifically constructed dynamical system approach (coupled selection equations) is used which is based on pattern formation principles and results in fault resistant and robust behaviour.

An important feature is that this type of control also guarantees feasibility of the assignment solutions. In previous work on adapting pattern formation principles to these problems either no feasibility is guaranteed or only unrealistic toy problems like one-step problems, i.e. no sequences of tasks, are treated.

These limitations are overcome in the present work where sequential manufacturing tasks in logical order are fully considered with guaranteed feasibility of the assignment solutions. The performance of the suggested control is demonstrated and visualized with a computer simulation of autonomous space robots building a space station by a distributed transportation of several parts from a space shuttle to defined positions at the space station.

Second, the suggested approach is used for the design and selection of traffic networks. The topology of the network is optimized with respect to an additive quantity like the length of route segments and an upper bound for the number of route segments. For this, the dynamics of the selection processes of the previous example is extended such that for each vertex several choices for the edges can be made simultaneously up to an individually given upper bound.

The final network topology emerges in a robust way as asymptotically stable state of the coupled selection equations. This behaviour can be guaranteed due to the specific omega limit set of the constructed dynamics and the corresponding basins of attraction. This is in parts joint work with R. Berkemer, C.

Ellsaesser, T. Fukuda, H. Haken, P. Molnar, M. Schanz.