Based upon an hierarchical world model with (virtual) roads we describe two different forms of cooperation. Asynchronous cooperation arises if preplanned trajectories of autonomous mobile robots with individual goals overlap. Synchronous cooperation takes place if several robots coordinate their actions in order to fulfill a collective task. We concentrate on all effects that result in the course of intersection passing. If a robot intends to pass an intersection and its destination road is occupied at its beginning the robot must not enter the intersection to keep it free. If there are mutual dependencies that result in a cycle no robot may proceed. We are faced with a deadlock that must be detected by all involved robots and resolved. While intersection passing in its regular form is an example for asynchronous cooperation, deadlock resolution shows cooperative synchronous behavior. The synchronized robots constitute a vehicle formation that moves as a unit at a higher organization level. We examine possible dependency graphs in traffic scenarios and explain the resulting data flow between the affected robots. We have taken care about the usability of our concepts in manufacturing and traffic.

Keywords: Decentralized robot system, asynchronous versus synchronous cooperation, deadlock detection and resolution, navigation, vehicle formation