School Seminars and Colloquia

Graph-based multi-agent coordination

ORSUM Seminar

by Dr Adrian Pearce


Institution: Department of Computer Science and Software Engineering, The University Melbourne
Date: Fri 3rd June 2005
Time: 1:05 PM
Location: Room 213, Richard Berry Building, Department of Mathematics and Statistics, University of Melbourne

Abstract: Agent programming languages frequently utilise a logical framework, where a
crucial component is the declarative part: initial state axioms,
precondition axioms and successor state axioms. The task is to find a
sequence of actions that constitute a legal execution of some high-level
nondeterministic program and this involves reasoning about preconditions and
effects of actions within the body of the program. This approach has been
recognised as one of the most successful solutions to non-deterministic
programming to date. However, current agent programming languages typically
model execution as sequences of states, and are rapidly becoming unworkable
due to the large number inter-dependencies frequently encountered: such as
the need to synchronise sub-tasks or resource conflicts. A fundamental
difficulty presently faced by programmers of multi-agent systems is the lack
of coordination algorithms when computational devices have overlapping or
common objectives or when agents rely on one-another to complete joints
tasks. The coordination problem is especially challenging where agents have
limited knowledge about, and control over, other agents. There is a great
need for improved methods for capturing and utilising richer dependency
information in distributed computation tasks in ways that guarantee more
effective and efficient solutions. Graph theoretic principles show great
promise for coordination of distributed tasks, since graphs capture richer
dependency information. The current states or epistemic beliefs of agents,
together with task dependencies, can be modelled by graphs in the form of
sets of labelled vertices connected by attributed edges. Although the use
of graphs have been studied in the literature, using dependency graphs
within and between groups; in terms of Kripke models or possible world
structures, formalising specific languages for this purpose is the subject
of ongoing work. Coordination algorithms which utilise graphs promise more
powerful coordination techniques; at the same time offering better
computation and communication efficiencies. Since graph approaches can
suffer complexity problems, particular attention must be paid to matching
and unification algorithms utilised. Recent developments in computationally
efficient graph matching techniques can lead to more powerful programming
techniques for multi-agent systems.

For More Information: Mark Fackrell tel. 8344-8053 email: m.fackrell@ms.unimelb.edu.au