Extract: Multi-Agent Scheduling
This is an extract from an extremely earlier draft of my Final Year Project. It's part of a topic that is likely to become a recurring theme in my posts for the next few months and, although this isn't the best place to start in terms of explaining it (this section is currently in a position some 12 pages into to the report), it represents an evening's work.
This post is going to be rather odd in that it's one I will actively dislike getting comments on...
There are some major issues with the simulation of multi-agent systems. For humans, time appears to be continuous — there is no truly indivisible unit of time — and everyone is capable of acting at any time. Because of this, we have issues with simultaneous actions: two people walking down a street may move in the same direction in order to avoid each other, with the net result that they are still on a collision vector. Similarly, when two people play “Rock, Paper, Scissors”, they each move at the ‘same’ time, with a variety of results: a victory, a loss, a draw, and occasionally some fun.
In contrast, simulations in a computer have to be designed to either work in time steps, or with only one agent acting a time, or (most often) with both of these constraints. Taking again the game of Rock Paper Scissors, this can create something of a problem — if one player plays before the other, then they might be able to observe there opponents move, and always win. This example is simple, and also simple to avoid — the players each submit a move, and then the moves are resolved (according to an ordering as needed). This issue is much larger with a slightly more complex game: consider a number of agents on a grid. Agents may move once per turn to an adjacent square; if it occupied, they ‘eat’ the agent that was on the square, removing it from the game. The objective, naturally is to be the last remaining agent.
Using time steps is already built into this problem, so simulation software will not fail in this way. However, if the agents play in a consistent order, the first agent has a clear advantage in that it can guarantee that it is not next to another agent at the end of its turn1. Assuming that this is the programming of all agents, the situation develops quickly into a stalemate. If the order in which turns are assigned is randomised, then some inherent ‘unfairness’ is introduced into the system — an agent may get two simultaneous moves, if it has both the last in one round and the first in the next round.
Both of these methods also suffer from the problem that only one agent is considering its turn at a time. If we have a concurrent system, where each agent decides on its move based purely one the state at the beginning of the round, it looks as if we will be able to avoid the ordering problem. However, once the orders are received by the control system, they have to be processed. Using a time ordering — moves being taken in the order that they are received — causes a large problem for consistent simulations, as the order of processing on a computer system is determined by an external scheduler. As the result of this kind of simulation is a function of the both the scheduler and the agents involved, the scheduler has to be known as part of the simulation in order to make it repeatable — a key feature of good simulations.
Thus, we are back to the situation that moves can be made without knowledge of the other agents actions, but those other actions can affect the outcome of one's own move — just as in “Rock, Paper, Scissors”, where your move alone does not win the game. Similarly, applying this system to the grid game, we can see the situation where two agents which start two squares apart might both chose to move to the same, intermediate, square. One will move, and then be eaten by the other, but the ordering is still scheduler dependent.
If a large number of agents see one resources is being over used, and another is being under used, this may result a large shift in favour of the less used resource. This behaviour is also seen in human queueing behaviour, as rush hour commuters know all too well. However, there is the potential for a huge amount of switching behaviour to be in a discrete system, which may lead to results being skewed.
There is also another problem with interfering moves — consider a variant of that game where the agents are aiming to collect prizes, and only one agent is permitted per square. If a collectable object appears between two agents, they should both move to collect it — however, only one will be able to claim it. In the non-concurrent case, this is not a major problem except in terms of fairness (if one agent will always see the new collectables before all the others). In the concurrent case, however, it can lead to agents attempting impossible moves, such as the second agent moving for the same collectable in this example.
Ensuring that moves are processed in a fair, safe, and repeatable way in a concurrent system is complex; just validating the safety of a concurrent system is an on-going area of research. The simple solution to simply drop all impossible actions entirely; this however means that certain agents are essentially not allowed to take their turns. More useful is to process the actions in some well-defined (although not necessarily constant) order, and allow agents who make impossible moves to retake there turn. This will reduce the overall efficiency of the processing, as agents will have to calculate the move repeatedly, and not at the same time as all the other agents.
Thus far, the scheduling problem has primarily seen like a purely fairness problem, which would in part be resolved by the fact that the equations for the management of Common Pool Resources are independent of the order in which either requests or votes arrive. This is predominately true, which is why a constant sequential ordering is used throughout.
This is an accurate enough model in the steady-state, but the initial stages may turn out to be more problematic, as large number of agents are trying to get organised into institutions and begin registering jobs, which may be shown as highly-variant transient behaviour in the early stages of the simulation.
- 1 ↑ Assuming that such a move is possible