Multi-Agent Systems
Agents & solving problems by communication
One of my primary research topics are autonomous agents and multi-agent systems. An agent is small computer program. It helps to model parts of the real world, such as products, machinery, elementary particles or even people.
This agent computer program has concepts for its satisfaction (utility) [1] and time, holds a memory to store its history, is able to listen and talk to other agents, and perhaps most important, it has models for forecasting the outcome of a decision.
In multi-agent system, several agents are foreseen and they can work together [2]. To do this, typically some sort of common language is required, so that the agents can talk with each other.
What purpose have agents?
- First of all, they are used by mathematicians to solve so-called called distributed constraint optimization [3,4] problems. These problems can be very complex and modelling the situation with agents is often not straightforward.
- A second use of agents is in modern IT systems. Of course, with distributed computing being a mandatory pre-condition for doing things like Big Data analytics, agents offer a convenient set of abilities to be applied here. Currently, as computer processor performances are no longer rising, parallel scaling of systems is the only way to improve execution times. Once you have a distributed computer system, e.g. a cluster with multiple nodes, you can distribute the agents among those nodes and let them solve problems in a parallel way. Agents introduce a sort of natural parallelisation here.
- In simulations of physical laws, agents can be used to represent physical players, such as electrons or interactions. Examples include here Monte-Carlo simulations describing particle transport.
One of my current research goals is to combine these advantages of agents together and let them solve mathematical optimisation tasks in distributed fashion, while representing real physical objects (in my case machinery of steel production).
Holons & coalition
Agents can form so-called coalitions with other agents to perform tasks. Once different species of agents must group together to solve a defined task, this coalition is called a holon [5]. In other words, without building the special holon, different agents or agent coalitions can in principle not be succesfull with their tasks, as certain skills are missing in their group.
Holons have become a popular mean in the optimization of production processes [6] as well as in the fields of scheduling and planning. An example holon from steel industry is shown in the figure, please click for enlarging it. Here, several "process" agents transform the "product" agent into its final state.
Application example: Virtual market structures in steel production
Let me show you in this work, how algorithms can improve modern manufacturing processes and, perhaps more important, can increase the profit out of the product. The presented system was developed by an European consortium consisting of ArcelorMittal, Centro Sviluppo Materiali, VDEh Betriebsforschungsinstitut (BFI), CETIC and Siemens [7]. Many people contributed to the success of this application.
Imagine that not all products go through a perfect production process. Then it may appear, that from time to time a product simply fails to meet the expectation of a customer. In the example of steel industy, a pretty simple case would be that a coil of steel was rolled to a wrong thickness. Nevertheless, these products have still a high quality. We would like to a) prevent the failure in advance or b) to reallocate the product to an alternative customer order. The latter would be a customer, who wants exactly this "wrong" thickness.
In many manufacturing companies, still the automation hierachy is kept strict and information flow from the production systems is rigorously reglemented. So our solution proposed to install software agents on diverse locations, talking to a service-oriented architecture layer on the databases to get access to data. A communication concept was developed, so that these agents can talk to each other, jointly reaching a common goal.
A big problem is, that we do not know exactly how the product will look like after the next process steps. The holons need this information in advance in order to trade problem products on a virtual marketplace, see first figure. Herein, two algorithms play an important role. First, there must be a prediction into the future,
The latter is a simplified, logistic model of the plants processes, where xi stands for any target value. Secondly, there must be a trading algorithm in the marketplace to conduct the auction of the products.
The agents can detect false products and propagate the information to future processing steps. There, the failure can be either corrected or the systems searches for an alternative product. In the beginning of 2015, a prototypical software system was installed at the industrial partners plants. It is currently performing real-world testing and shows very successful results. We disseminated the results of the work at the European Steel and Application Days 2015 during the METEC trade fair, in Duesseldorf. More detailed information including the slides of my talk can be found on researchgate.
Bibliography
[1] Shoham, Y. & Leyton-Brown, K., Multiagent Systems, Stanford University, 2009
[2] Vidal, J. M., Fundamentals of Multiagent Systems, 2010
[3] Yokoo, M.; Durfee, E. H.; Ishida, T. & Kuwabara, K., The Distributed Constraint Satisfaction Problem: Formalization and Algorithms, IEEE Trans. on Knowledge and Data Engineering, 1998, 10
[4] Modi, P. J.; Shen, W.-M.; Tambe, M. & Yokoo, M., ADOPT: Asynchronous Distributed Constraint Optimization with Quality Guarantees
[5] Leitao, P. & Restivo, F., ADACOR: a holonic architecture for agile and adaptive manufacturing control, Comput. Ind., Elsevier Science Publishers, B. V., 2006, 57, 121-130
[6] Barbosa, J; Self-organized and evolvable holonic architecture for manufacturing control. Chemical and Process Engineering, Université de Valenciennes et du Hainaut-Cambresis, 2015
[7] Marcus J. Neuer (BFI), Francesca Marchiori (CSM), Alexander Ebel (BFI), Nikolaos Matskanis (CETIC), Luca Piedemonti (CSM), Andreas Wolff (BFI) and GaelMathis (ArcelorMittal), Dynamic rescheduling and reallocation of steel products using agents with strategical anticipation and virtual marketstructures, IFAC 2016