Discrete-event multiagent coordination : framework and algorithms
Manh Tung Pham · 2011
This thesis proposes a formal design framework for three inter-agent coordination problems that have not been addressed in the literature: A fundamental coordination problem, a networked coordination problem and an on-line coordination problem.The problems arise when distributed agents need to interact and communicate among themselves in order to guarantee conformance to some inter-agent constraints that restrict their behaviors.These problems are formulated and addressed for a class of agents in a discrete-event behavioral formalism.The basic solution proposed is to equip agents with some distributed, local cooperation mechanism called coordination modules (CM's), by which they can compute their local coordinating actions in response to each other's information update.The framework developed supports the automated synthesis of CM's for discrete-event agents.The fundamental problem is formulated as synthesizing CM's for multiple agents coordinating to satisfy one pre-specified inter-agent constraint.A fundamental insight unearthed is that discrete-event agent coordination shares the same algorithmic foundation with related problems in the control literature although they are conceptually different domains.This insight leads to the adaptation and extension of related control and observation concepts for the development of a new concept called coordinable language, which is shown to be the necessary and sufficient existence condition of CM's for distributed agents.A new CM synthesis algorithm is developed for the fundamental problem.The networked coordination problem generalizes the fundamental problem to multiple pre-specified inter-agent constraints distributed among agents.In addressing the problem, the originality of our solution approach emanates from two major research ideas.The first is in proposing a new formalism called the Distributed Constraint Specification Network (DCSN) that can comprehensibly describe the networking constraint relationships among the agents, with every constraint and the group of agents that it is relevant for forming a basic subnet.Each basic subnet of a DCSN therefore specifies a fundamental coordination