Computer Engineering and Applications ›› 2010, Vol. 46 ›› Issue (22): 1-3.DOI: 10.3778/j.issn.1002-8331.2010.22.001

• 博士论坛 • Previous Articles     Next Articles

Generalized Voronoi diagrams for multiple robots motion planning

FENG Hong-kui1,BAO Jin-song1,2,JIN Ye1,2   

  1. 1.Institute of Computer Integrated Manufacturing,Shanghai Jiaotong University,Shanghai 200240,China
    2.Shanghai Key Laboratory of Advanced Manufacturing Environment,Shanghai 200240,China
  • Received:2010-01-05 Revised:2010-05-31 Online:2010-08-01 Published:2010-08-01
  • Contact: FENG Hong-kui

广义Voronoi图求解多机器人运动规划

冯洪奎1,鲍劲松1,2,金 烨1,2   

  1. 1.上海交通大学 计算机集成制造研究所,上海 200240
    2.上海市网络化制造与企业信息化重点实验室,上海 200240
  • 通讯作者: 冯洪奎

Abstract: In a populated environment,boundaries of obstacles are complex,and Generalized Voronoi Diagrams(GVDs) are employed to represent the spatial environment.In the motion planning for multiple robots,it must be considered for coordinating these robots according to passage width in the constructed GVDs.Thus an algorithm for computing the passage width in the constructed GVDs according to the populated environment is proposed.A* algorithm is employed for planning paths for multiple robots in the constructed GVDs,and a distributed method is used for coordinating motions of multiple robots.An instance for coordinating two robots is given and simulated.The simulation results show that the multiple robot motion planning can be completed based on the GVDs with passage width.

摘要: 在拥挤环境中,由于障碍物的边界形状比较复杂,需要使用广义Voronoi图表示空间环境。且在多移动机器人的运动规划过程中,需要协调多个机器人的运动,必须得到Voronoi图通道的宽度。为此提出了一种计算拥挤障碍物环境中生成的广义Voronoi图及其通道宽度的算法。并在生成的Voronoi图上利用A*算法对多个机器人进行路径规划,并利用分布式方法协调多个机器人运动。对协调两个机器人运动的过程进行了仿真,仿真结果表明利用提出的算法生成的具有通道宽度信息的Voronoi图能够满足多移动机器人运动规划的需要。

CLC Number: