中国物理B ›› 2009, Vol. 18 ›› Issue (8): 3104-3114.doi: 10.1088/1674-1056/18/8/002

• • 上一篇    下一篇

Automatic generation of min-weighted persistent formations

罗小元, 李绍宝, 关新平   

  1. Department of Electrical Engineering, Yanshan University, Qinhuangdao 066004, China
  • 收稿日期:2008-12-13 修回日期:2008-12-31 出版日期:2009-08-20 发布日期:2009-08-20
  • 基金资助:
    Project supported by the National Natural Science Foundation for Distinguished Young Scholars of China (Grant No 60525303), the National Natural Science Foundation of China (Grant No 60704009) and Doctor Fund of Yanshan University (Grant No B203).

Automatic generation of min-weighted persistent formations

Luo Xiao-Yuan(罗小元)†, Li Shao-Bao(李绍宝), and Guan Xin-Ping(关新平)   

  1. Department of Electrical Engineering, Yanshan University, Qinhuangdao 066004, China
  • Received:2008-12-13 Revised:2008-12-31 Online:2009-08-20 Published:2009-08-20
  • Supported by:
    Project supported by the National Natural Science Foundation for Distinguished Young Scholars of China (Grant No 60525303), the National Natural Science Foundation of China (Grant No 60704009) and Doctor Fund of Yanshan University (Grant No B203).

PDF (PC)

893

赞

摘要： This paper researched into some methods for generating min-weighted rigid graphs and min-weighted persistent graphs. Rigidity and persistence are currently used in various studies on coordination and control of autonomous multi-agent formations. To minimize the communication complexity of formations and reduce energy consumption, this paper introduces the rigidity matrix and presents three algorithms for generating min-weighted rigid and min-weighted persistent graphs. First, the existence of a min-weighted rigid graph is proved by using the rigidity matrix, and algorithm 1 is presented to generate the min-weighted rigid graphs. Second, the algorithm 2 based on the rigidity matrix is presented to direct the edges of min-weighted rigid graphs to generate min-weighted persistent graphs. Third, the formations with range constraints are considered, and algorithm 3 is presented to find whether a framework can form a min-weighted persistent formation. Finally, some simulations are given to show the efficiency of our research.

Abstract: This paper researched into some methods for generating min-weighted rigid graphs and min-weighted persistent graphs. Rigidity and persistence are currently used in various studies on coordination and control of autonomous multi-agent formations. To minimize the communication complexity of formations and reduce energy consumption, this paper introduces the rigidity matrix and presents three algorithms for generating min-weighted rigid and min-weighted persistent graphs. First, the existence of a min-weighted rigid graph is proved by using the rigidity matrix, and algorithm 1 is presented to generate the min-weighted rigid graphs. Second, the algorithm 2 based on the rigidity matrix is presented to direct the edges of min-weighted rigid graphs to generate min-weighted persistent graphs. Third, the formations with range constraints are considered, and algorithm 3 is presented to find whether a framework can form a min-weighted persistent formation. Finally, some simulations are given to show the efficiency of our research.

Key words: min-weighted persistent graph, rigidity matrix, minimally rigid graph, formation, multi-agent

中图分类号:  (Combinatorics; graph theory)

  • 02.10.Ox
02.10.Yn (Matrix theory) 02.30.Yy (Control theory) 84.40.Ua (Telecommunications: signal transmission and processing; communication satellites) 89.75.Hc (Networks and genealogical trees)