Aladdin

We derive a novel decentralised technique for planning agent schedules in dynamic task allocation problems. Specifically, beginning with a Markov game formulation of these problems, we introduce a new technique for approximating this game using a series of static potential games, and solve these static games using the Distributed Stochastic Algorithm. We call this approach the overlapping potential games algorithm, or OPGA. The video presents an implementation of OPGA for a task allocation problem in the RoboCup Rescue disaster management simulator. Our results show that, unlike a state-of-the-art centralised task scheduler, OPGA is robust to restrictions on the agents' communication range, which is a commonly encountered limitation in real-world problems.

These two videos show two examples of the pursuit evasion domain. In both videos, three mobile agents (red circles) are searching for an evader (the yellow square) within the Intelligence, Agents, Multimedia lab of the School of Electronics and Computer Science. The size of the vertices is proportional to the probability of the evader being there. In the first video, the evader moves randomly. In the second video, the evader continuously moves away from the closest agent. We call this a smart evader.

This video shows four mobile agents monitoring an environmental phenomena, who coordinate their movements using the max-sum algorithm. The contour lines connect points with equal prediction error (lower is better). Furthermore, agents are incentivised to maintain network connectivity–a technique that is described in Section 4.3. As shown in this video, this technique is effective: the agents' communication network is connected at all times.

Demonstration of the VPI approach to sequential decision making under uncertainty to select teams within the Robocup Rescue Simulator. In this scenario, fire brigades have uncertain capabilities, which means each of them may work differently in different teams, and therefore affect the team performance in extinguishing fires of particular kinds. Ideally, the agents should be able to form the best groups (with the required capabilities) to extinguish specific fires. The colours represent the match between capability and fires. The aim is to optimise the overall performance of the set of agents.

The evacuation of a building is a challenging problem, since the evacuees most of the times do not know or do not follow the optimal evacuation route. Especially during an ongoing hazard present in the building, finding the best evacuation route becomes harder as the conditions along the paths change in the course of the evacuation procedure. We propose a distributed system that will compute the best evacuation routes in real-time, while a hazard is spreading inside the building. The system is composed of a network of decision nodes and sensor nodes, positioned in specific locations inside the building. The recommendations of the decision nodes are computed in a distributed manner, at each of the decision nodes, which then communicate them to evacuees or rescue personnel located in their vicinity. The scenario demonstrated involves the evacuation of a three storey building. There are two exits located on the ground floor, while a fire starts in the second floor of the building. The arrows represent the directions that an evacuee receives from a Decision Node. Each evacuee decides its next destination based on this recommendation.

We are developing buyer and seller strategies for online auctions that permit the efficient allocation of goods and tasks in environments where agents are selfish and rational. These strategies allow agents to maximise their utility when bidding in multiple auctions at the same time. The project has generated a number of papers on the subject and these can be found on the Publications page. The auction demos feature a number of ambulance centers that are responsible for rescueing trapped civilians in different parts of the map. We consider three different cases. Click on the link to see a video of each case:

• No Auctions: each center has a limited number of ambulances to save the civilians. The centers cannot share their resources since there exists no mechanism to do so dynamically in the case of major disasters..
• Dynamic Auctions: the ambulances are maintained by one central authority. Whenever centers feel the need for a number of ambulances, they bid for the required number of ambulances according to the criticality of the civilians' health. As soon as the proposed rescue task is completed by the hired ambulance, the latter is returned to the central authority which re-auctions it to prospective bidding centers.
• Distributed Auctions: each center has a number of ambulances to perform a number of rescue tasks. However, some of them may require more ambulances than they currently have and others may require less. Then, those excess ambulances are auctioned off and centers that need ambulances bid for these. The ambulances are allocated to the highest bidder (i.e. relative to the criticality of the civilian to be saved). When the ambulance has finished its task it is returned to its owner. Moreover, the demo shows that if a center fails, the ambulances can easily be re-allocated to the adjacent center and the dynamic allocation can be performed as before.

n order to coordinate a number of agents (e.g. ambulances or fire brigades) efficiently, it is important to distribute them in a number of efficient teams coalitions. Given $N$ agents, the number of coalitions that could be generated is 2^N. Moreover, each coalition may have a value which represents how efficiently it can perform tasks. This may be due to differences in capabilities or constraints. Now, it is important to select the best coalitions and this problem is termed the coalition structure generation problem. We have developed the fastest algorithm for this purpose and a paper describing our algorithm can be found here. To demonstrate the coalition structure generation process in our simulator, we show how a number of ambulances owned by a single center can split up into a number of efficient coalitions in order to rescue a number of civilians in the environment.

Distributed decision making with limited communication implies that dinstinct rescuers must act without coordination during the decision process. We have developed a novel algorithmic approach based on designing an "oracle" that uses a neural network for mapping input information into allocation of destinations for the rescuers. The specific neural network model is the RNN with synchronised interactions which we train with situations that are similar to those encountered during an emergency. In the demonstrated scenario, the rescuers have an initial, incorrect estimation of the number of injured civilians. When a rescuer visits an injury location, he informs the others about the correct number of injured civilians and then each rescuer individually uses his "oracle" to decide whether to change or not destination.

In this scenario we demonstrate the use of smart on-line algorithms that provide directions regarding the best available path towards an exit during a building evacuation in the presence of a hazard. The technical approach is based on a network of sensor and decision nodes positioned in specific locations. The paths that can be followed by an evacuee or by emergency personnel can be linked to progress along the decision and sensor nodes. Each sensor node is location aware and able to sense information regarding the environment, such as hazard intensity and location.Such algorithms can be used in practice with either “visible panel” indicators in the building which are controlled by the path finding algorithm, or via data exchanged between wireless nodes and portable communication devices (such as a PDAs) carried by the evacuees and the emergency personnel.