This paper contributes to the multiagent constraint framework for synthesizing correct local plans and coordination strategies for every participating agent, and meeting their local goals without conflict or blocking. Existing work has focused mainly on developing conflict resolution algorithms for various different types of constraint systems. This paper addresses a new but related problem called multiagent conflict resolution planning for multiple coordination plans. To resolve all potential conflicts between multiagent plans, the problem is to be able to efficiently plan and intelligently select an optimal process plan showing the sequential or partial orders of applying conflict resolution algorithms. A generic approach to the problem is developed that is applicable to various types of constraint systems. Two new innovations are proposed: (1) A comprehensible network model that shows the relationships between agents and their constraints, and (2) a compact AND/OR graph representation of conflict resolution (process) plans. An AND/OR graph plan generation algorithm is proposed and evaluated. The selection of an optimal conflict resolution plan over the AND/OR graph representation is discussed. A case study is presented.

In control of discrete-event systems (DESs), specifying control requirements in automata is not a trivial task. For many DES applications, designers are often confronted with the long-standing problem of uncertainty in specification, namely, how do we know that a specification automaton does indeed model the intended control requirement? Toward a formal framework that helps mitigate this uncertainty for designer comprehensibility, in this paper, we introduce and develop a new specification concept of automaton transparency and investigate the problem of maximizing the transparency of specification automata for DESs. In a transparent specification automaton, events that are irrelevant to the specification but can occur in the system are “hidden” in self-loops. Different automata of the same specification on a DES can be associated with different sets of such irrelevant events, and any such automaton is said to be the most transparent if it has an irrelevant event set of maximal cardinality. The transparency maximization problem is theoretically formulated, and a provably correct solution algorithm is obtained. Given a specification automaton for a DES, the transparent specification automaton produced by the algorithm is a more comprehensible structure, essentially showing the precedence ordering among events from a minimal cardinality set that is relevant in modeling some requirement for the DES, and should aid designers in clarifying if the requirement prescribed is the one intended.

This paper presents new results on the formal design of distributed coordinating agents in a discrete-event framework. In this framework, agents are modeled to be individually equipped with a coordination module, through which they interact and communicate. In terms of existing control-theoretic concepts, we first define the concept of a coordinable language and show that it is the necessary and sufficient existence condition of coordination modules for distributed agents to achieve conformance to a prespecified interagent constraint language. Following, we present a synthesis algorithm to compute near-optimal coordination modules. An example is provided to illustrate the design synthesis using the proposed algorithm. Finally, a discussion with related work distinguishes our coordination design problem from related problems in the literature.

This paper addresses a novel coordination problem for distributed agents in a discrete-event setting. We first introduce and study a predicate coordination problem as the problem of two distributed agents interacting and communicating between themsel

The problem of maximizing the transparency of specification automata for discrete event systems (DES's) is investigated. In a transparent specification automaton, events that are irrelevant to the specification but can occur in the system are `hidden' in self-loops. Different automata of the same specification on a DES can be associated with different sets of such irrelevant events; and any such automaton is said to be the most transparent if it has an irrelevant event set of maximal cardinality. The transparency maximization problem is theoretically formulated and a provably correct solution algorithm is obtained. The most transparent specification automaton essentially shows the precedence ordering among events from a minimal cardinality set that is relevant to the intended requirement, and should help towards resolving the long-standing problem in specification, namely: how do we know that a specification in automata does indeed capture the intended control requirement?