Direction problem in leader-follower formations of unmanned aerial vehicles and satellite clusters

This paper is concerned with information structures used in rigid formations of unmanned aerial vehicles (UAV’s) and micro-satellite clusters that have leader-follower architecture. The focus of the paper is on sensor/network topologies to secure control of rigidity. Specifically, we study the problem of determining the directions of links of an undirected formation so that the resulting formation is rigid, which is called the “Direction Problem.” The algorithm given in the paper establishes a sequential way of determining the directions of links in a leader-follower formation from a given undirected rigid formation. The algorithm is related to our simpler process of finding two spanning trees, as well as the counts in Laman’s Theorem. In common with tree finding algorithms, it is greedy, so the order of testing edges does not effect the size of maximal independent sets found, or the distribution of the edges through the UAV’s and micro-satellites.

___

[1] Belta, C., and Kumar, V., “Abstraction and control for groups of robots,” IEEE Transactions on Robotics, vol. 20, no. 5, pp. 865–875, 2004. [2] Olfati-Saber, R., and Murray, R., “Graph rigidity and distributed formation stabilization of multi-vehicle systems,” in Proceedings of the 41st IEEE Conference on Decision and Control, Las Vegas, NV, December 2002. [3] Tabuada, P., Pappas, G., and Lima, P., “Feasible formations of multi-agent systems,” IEEE Transactions on Robotics, vol. 21, no. 3, pp. 387–392, 2005. [4] Tanner, H., Pappas, G. J., and Kumar, V., “Leader-to-formation stability,” IEEE Transactions on Robotics and Automation, vol. 20, no. 3, pp. 443–455, June 2004. [5] Baillieul, J., and Suri, A., “Information patterns and hedging Brockett’s theorem in controlling vehicle formations,” in Proceedings of the 42nd IEEE Conference on Decision and Control, Maui, Hawaii, December 2003. [6] Zhang, F., Grocholsky, B., and Kumar, V., “Formations for localization of robot networks,” in Proceedings of the 2004 IEEE International Conference on Robotics and Automation, April 2004. [7] Ren, W., and Beard, R. W., “A decentralized scheme for spacecraft formation flying via the virtual structure approach,” AIAA Journal of Guidance, Control and Dynamics, vol. 27, no. 1, pp. 73–82, January 2004. [8] Lin, Z., Francis, B., and Maggiore, M., “Necessary and sufficient graphical conditions for formation control of unicycles,” IEEE Trans. Automatic Control, vol. 50, no. 1, pp. 121–127, 2005. [9] Das, A., Fierro, R., Kumar, V., and Ostrowski, J., “A vision-based formation control framework,” IEEE Trans. on Robotics and Automation, vol. 18, no. 5, pp. 813–825, 2002. [10] Gazi, V., and Passino, K., “Stability analysis of swarms,” IEEE Trans. On Automatic Control, vol. 48, no. 4, pp. 692–697, 2003. [11] Eren, T., Anderson, B.D.O., Morse, A.S., Whiteley, W., and Belhumeur, P.N., “Operations on rigid formations of autonomous agents,” Communications in Information and Systems, vol. 3, no. 4, 2004. [12] Eren, T., Whiteley, W., Anderson, B. D. O., Morse, A. S., and Belhumeur, P. N., “Information structures to secure control of rigid formations with leader-follower architecture,” in Proceedings of the American Control Conference, Portland, Oregon, June 2005, pp. 2966–2971. [13] Yu, C., Fidan, B., and Anderson, B. D. O., “Persistence acquisition and maintenance for autonomous formations,” in Proceedings of Workshop on Unmanned Aerial Vehicles, 2nd International Conference on Intelligent Sensors, Melbourne, Australia, December 2005, pp. 379–384. [14] Marshall, J., Broucke, M., and Francis, B., “Formations of vehicles in cyclic pursuit,” IEEE Trans. Automatic Control, vol. 49, no. 11, pp. 1963–1974, 2004. [15] Eren, T., Belhumeur, P., Anderson, B.D.O., and Morse, A.S., “A framework for maintaining formations based on rigidity,” in Proceedings of the 15th IFAC World Congress, Barcelona, Spain, July 2002, pp. 2752–2757. [16] Eren, T., Belhumeur, P.N., and Morse, A.S., “Closing ranks in vehicle formations based on rigidity,” in Proceedings of the 41st IEEE Conference on Decision and Control, December 2002, pp. 2959–2964. [17] Eren, T., Whiteley, W., and Belhumeur, P.N., “Rigid formations with leader-follower architecture,” Columbia University, Tech. Rep. CUCS-010-05, March 2005. [Online]. Available: http://www1.cs.columbia.edu/~library/ [18] Eren, T., Whiteley, W., and Belhumeur, P.N.,, “Rigid formations with leader-follower architecture,” Columbia University, Tech. Rep. CUCS-008-06, December 2005. [Online]. Available: http://www1.cs.columbia.edu/~library/ [19] Whiteley, W., “Rigidity and scene analysis,” in Handbook of Discrete and Computational Geometry, J. Goodman and J. O’Rourke, Eds. CRC Press, 1997, pp. 893–916. [20] Roth, B., “Rigid and flexible frameworks,” American Mathematical Monthly, vol. 88, pp. 6–21, 1981. [21] Whiteley, W., “Matroids from discrete geometry,” in Matroid Theory, J. E. Bonin, J. G. Oxley, and B. Servatius, Eds. American Mathematical Society, Contemporary Mathematics, 1996, vol. 197, pp. 171–313. [22] Connelly, R., “On generic global rigidity,” June 2003, preprint, Cornell University, Ithaca, New York, USA. [23] Servatius, B., and Servatius, H., “Generic and abstract rigidity,” in Rigidity Theory and Applications, M. Thorpe and P. Duxbury, Eds. Kluwer Academic/Plenum Publishers, 1999, pp. 1–19. [24] Laman, G., “On graphs and rigidity of plane skeletal structures,” Journal of Engineering Mathematics, vol. 4, pp. 331–340, 2002. [25] Hendrickson, B., “An algorithm for two-dimensional rigidity percolation: The pebble game,” Journal of Computational Physics, vol. 137, pp. 346– 365, 1997. [26] Jacobs, D., and Thorpe, M., “Generic rigidity percolation: The pebble game,” Physical Review Letters, vol. 75, no. 22, pp. 4051–4054, 1995.