TY - GEN
T1 - A method of constructing complete graph for multi-objects path planning in complex environment
AU - Gao, Bo
AU - Yan, Weisheng
AU - Zhang, Fubin
AU - Wang, Yintao
PY - 2009
Y1 - 2009
N2 - Considering path planning for multi-objects in complex environment, the construction of complete graph which reflects the relative distance between objects in real world has great influence on calculating the sequence of objects and the optimal path throughout the optimization and path planning algorithm. This paper describes an approach that integrates the representations of uniform grids and Voronoi diagrams to build the complete graph in complex environment for multi-objects. It firstly generates an initial Voronoi diagram with respect to the obstacle regions in the cost-changing and complex environment on top of grid-based maps. We then uses the techniques from path planning to make modifications by partitioning the obstacles into coherent regions and updating the Voronoi diagram considering the relationship between objects and obstacles. Finally the complete graph is built from the modified Voronoi diagram. Throughout the simulation, such a method of building the complete graph could make the outcome of path planning better compared with the complete graph from Euclidean distance.
AB - Considering path planning for multi-objects in complex environment, the construction of complete graph which reflects the relative distance between objects in real world has great influence on calculating the sequence of objects and the optimal path throughout the optimization and path planning algorithm. This paper describes an approach that integrates the representations of uniform grids and Voronoi diagrams to build the complete graph in complex environment for multi-objects. It firstly generates an initial Voronoi diagram with respect to the obstacle regions in the cost-changing and complex environment on top of grid-based maps. We then uses the techniques from path planning to make modifications by partitioning the obstacles into coherent regions and updating the Voronoi diagram considering the relationship between objects and obstacles. Finally the complete graph is built from the modified Voronoi diagram. Throughout the simulation, such a method of building the complete graph could make the outcome of path planning better compared with the complete graph from Euclidean distance.
UR - http://www.scopus.com/inward/record.url?scp=70449635295&partnerID=8YFLogxK
U2 - 10.1109/ICINFA.2009.5204957
DO - 10.1109/ICINFA.2009.5204957
M3 - 会议稿件
AN - SCOPUS:70449635295
SN - 9781424436088
T3 - 2009 IEEE International Conference on Information and Automation, ICIA 2009
SP - 403
EP - 407
BT - 2009 IEEE International Conference on Information and Automation, ICIA 2009
T2 - 2009 IEEE International Conference on Information and Automation, ICIA 2009
Y2 - 22 June 2009 through 25 June 2009
ER -