Info: Cite as: A Decentralized Approach to Cooperative Situation Assessment
in Multi-Robot Systems, G. P. Settembre, P. Scerri, A. Farinelli, K. Sycara,
and D. Nardi, Proc. of 7th Int. Conf. on Autonomous Agents and Mul-
tiagent Systems (AAMAS 2008), Padgham, Parkes, Müller and Parsons
(eds.), May, 12-16., 2008, Estoril, Portugal, pp. XXX-XXX.
Copyright ⃝c 2008, International Foundation for Autonomous Agents and
Multiagent Systems (www.ifaamas.org). All rights reserved.
I picked up another paper which focusses on robot co-ordination in a slightly different way, by combining observations from the robots to come to a group decision. The Max Sum literature I've been reading has been very instructive, and having been directed to the author Professor Paul Scerri and finding this paper, I thought it worthwhile exploring alternative methods for agent co-ordination. It seems the case that Max-Sum is extremely adept at the UAVs-over-a-disaster-zone scenario, but since our UAV team is possibly going to be dealing with slightly different tasks in the near future a broad knowledge of some problem solving algorithms seems useful. This particular example was tested on a computer model of UGVs in a search space.
The algorithm (referred to only as the MAS [Multi Agent System] Policy) involves essentially transposing an argumentative framework into a situation where the agents are working together. Rather than having message passing and a form of argumentative negotiation to ensure your best gains (such as might be encountered in bidding software), they use this method to challenge plans of action based on each robot's own data gathered about the world, and their 'belief' in a certain set of circumstances. Optimal plans of action are known by each agent in advance, and using their own 'beliefs' they can compute what they believe to be the best course of action, given especially that they don't know their belief to be definitely true.
For example, in a burning building if the robot encounters what it recognises as a human, which it believes to be moving, is it best to implement a plan to get the human to follow the robot out of the building? Or is it better; depending on the exact level of belief; to assume the human is unconscious and remotely summon the emergency services to that location?
Such decision making turns out to be surprisingly in-depth. The model relies on the basic principles that as-specific a solution as possible is best, but a general solution is better than being wrong. So in the above example, leading the human out would be best if they were conscious, but it would be less-bad to call the firefighters if they were conscious than trying to lead them out if they were unconscious. Applying numerical values to different scenarios effectively determines an individual robot's ultimate plan.
Once a robot has worked out what it believes to be the best plan of action, the message passing begins. The robot tells a random neighbour its plan. The neighbour may just agree, and pass the message on. But, it may have its own beliefs which affect the plan:
In this case, the first robot can either stick to its guns and send its original plan back to the arguer, along with its own data to support its case, or it can change its mind. Every time an agreement is reached the message is sent on randomly until a prerequisite number of robots have agreed with the plan.
The paper itself points out two down-sides to this arrangement. Firstly it produces poor decisions in scenarios with too few robots (and therefore, not enough data to share around). Secondly dynamic environments constantly changing will result in outdated information by the time an agreement is reached. In practice, this places some restrictions on what sort of tasks might be carried out. Specifically information density is key and this would clearly not be suitable in a sparsely populated environment (say, a handful of UAVs in a large search area).
The paper records performance examples as being almost as good as a central situation where every robot knows all the information gained by every other robot. Clearly this is unfeasible in terms of message sizes being passed...
Final thought
Indeed, this is where I think this method falls down. Compared to something like Max Sum, which is specifically optimised to minimise interaction, this algorithm seems to carry a huge message overhead which could increase polynomially with the number of agents and the amount of agreement required. It could still prove feasible in a densely populated environment but as-yet, it seems a little too specific.
-C
No comments:
Post a Comment