Rigid Formations with Leader-Follower Architecture

Eren, Tolga; Whiteley, Walter; Belhumeur, Peter N.

This paper is concerned with information structures used in rigid formations of autonomous agents that have leader-follower architecture. The focus of the paper is on sensor/network topologies to secure control of rigidity. This papers extends the previous rigidity based approaches for formations with symmetric neighbor relations to include formations with leader-follower architecture. We provide necessary and sufficient conditions for rigidity of directed formations, with or without cycles. We present the directed Henneberg constructions as a sequential process for all guide rigid digraphs. We refine those results for acyclic formations, where guide rigid formations had a simple construction. The analysis in this paper confirms that acyclicity is not a necessary condition for stable rigidity. The cycles are not the real problem, but rather the lack of guide freedom is the reason behind why cycles have been seen as a problematic topology. Topologies that have cycles within a larger architecture can be stably rigid, and we conjecture that all guide rigid formations are stably rigid for internal control. We analyze how the external control of guide agents can be integrated into stable rigidity of a larger formation. The analysis in the paper also confirms the inconsistencies that result from noisy measurements in redundantly rigid formations. An algorithm given in the paper establishes a sequential way of determining the directions of links from a given undirected rigid formation so that the necessary and sufficient conditions are fulfilled.



More About This Work

Academic Units
Computer Science
Department of Computer Science, Columbia University
Columbia University Computer Science Technical Reports, CUCS-008-06
Published Here
April 26, 2011