Agent specification and programming languages

The Agentlab is actively developing agent specification and programming languages for implementing complex tasks robustly and efficiently. Research is currently focused on languages that allow for bridging of levels of abstraction and guaranteeing certain properties within these multi-agent systems.

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.

Research includes the integration of graph theory into the model-theoretic approaches normally associated with the agent programming, including the explicit representation of agent roles and intentions via Role-graphs, and coordination strategies for scheduling among teams of agents, including the Provisional-agreement Protocol (PAP).

Contact: Adrian Pearce

Publications: Agent specification and programming languages