Ph.D Thesis

Ph.D StudentResmerita Stefan
SubjectA Multi-Agent Approach to Control of Multi-Robotic
DepartmentDepartment of Computer Science
Supervisors PROF. Michael Heymann
PROF. Ehud Rivlin


The thesis has two main topics of research: conflict resolution in multi-agent systems, and the Zenoness phenomenon in hybrid systems.

The first part deals with the problem of controlling multiple robots in a planar domain. We consider a discrete model, where the domain (the common resource) is partitioned into cells. A safety requirement demands that at most one robot may occupy a cell (resource) at a time. The resource system is modeled by an undirected graph, where a vertex corresponds to a cell and an edge represents an adjacency relation between two cells. A robot must travel from an initial vertex to a destination vertex. A robot trajectory is a timed directed path in the resource graph, starting at the initial vertex and ending at the destination vertex. Each transition in the path specifies the time of residence at the preceding vertex. A liveness specification requires that a robot occupying a cell (active robot) has at least one conflict-free path to the destination. The number of robots is not specified. A robot exits the system upon task completion, and robots can enter the system at arbitrary (integer) moments of time.

We propose a distributed framework, where a robot is an autonomous agent. An agent is required to declare all of its optimal paths (according to some criteria), its movement being confined to this optimal set. The problem is how agents should select their legal paths, such that safety, liveness, and efficient resource utilization are achieved. By efficient resource utilization, we understand maximal permissiveness with respect to allowing incoming agents to enter the system. We present a distributed and maximally permissive approach, consisting of two main phases. In the first phase, incoming agents resolve conflicts among them, based on a given prioritization over disputed resources (where an agent can have different priorities for different resources). We present an optimal algorithm for conflict resolution, which always obtains a solution that cannot be improved by a single agent without creating a conflict with some other agent. In the second phase, the active agents accommodate agents which have obtained nothing in the first phase. We present an accommodation protocol, where an agent can ask and receive resources from other agents in the system. This approach always finds a solution for the accommodation of an incoming agent, if one exists.

The second part deals with conditions for existence of Zeno behaviors in hybrid systems. These may arise when a discrete controller attempts to satisfy specified state invariance constraints by forcing the system to undergo an unbounded number of discrete transitions in a bounded time. We present a method for detection of Zenoness of a class of hybrid systems, as well as new insights on synthesis of safety controllers, as related to Zenoness. Our approach is based on a certain “reachability equivalence” between a hybrid system and a continuous sytem.