A Game-Theoretic Analysis of Multi-Agent Systems for Shop Floor Routing

Technical Report CMU-RI-TR-01-28, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA, .



In recent years, the desire for a more robust basis for coordination in manufacturing environments has motivated research into agent-based approaches to manufacturing scheduling and control. We have been developing a series of such multi-agent systems inspired by models of social insect behavior for the problem of dynamic shop floor routing. To date, all of our results have been empirical in terms of global system performance and we have been without any satisfying explanation for the behavior of the interacting agents of these systems. This paper is an attempt to model these interactions in game-theoretic terms as normal form games. In the analysis, we show that the behavior of the agents in a repeated game scenario appears to converge upon the repeated play of Nash Equilibria (NE). This analysis consists of the examination of games corresponding to specific problem instances. Some of the systems in this study tend to converge upon deficient NE; while the others successfully coordinate upon "better" equilibria on a consistent basis.