2003年3月

第21卷第1期　长沙铁道学院学报

JOURNALOFCHANGSHARAILWAYUNIVERSITY　Mar.2003

文章编号:100022499(2003)0120052205

平面移动机器人最短路径规划的几何算法研究

易　晟,樊晓平,罗　熊Ξ

(中南大学自动化工程研究中心,湖南长沙　410075)

摘　要:平面移动机器人最短路径规划算法在许多领域有着十分广泛的应用.利用图论和Dijkstra算法研究了在由大尺度简单多边形(只在公共顶点相交的边组成的多边形)障碍物组成的平面场景中,平面移动机器人最短路径规划的几何算法,编制了仿真实现程序,给出了仿真结果.

关键词:移动机器人;最短路径规划;多边形;凸凹性;Dijkstra算法

中图分类号:TP24　　　文献标识码:A

StudyonGeometricAlgorithmofShortestPath

PlanningforPlanarMobileRobot

YISheng,FANXiao2ping,LUOXiong

(ResearchCenterforAutomationEngineering,CentralSouthUniversity,Changsha410075,China)

Abstract:Shortestpathplanningoftheplanarmobilerobotiswidelyusedinmanyfields.BasedonGraphTheoryandDijkstraalgorithm,thispapermakesthoroughanalysisofgeometricalgorithmofshortestpathplanningunderthecircumstanceswheretheobstaclesarecomposedofconvexorconcavepolygons.Thesimulationprogramisachievedandtheresultisalsopresented.

Keywords:mobilerobot;shortestpathplanning;polygonconcave;convex;Dijkstraalgorithm

1　概　述

所谓机器人的最优路径问题,是依据某一个或某一些优化标准(如代价最小、行走路线最短等),在其工作环境中找出一条从起点到终点的能避开障碍物的最优行走路径.最优路径算法在军事、交通、地理、城市规划等方面有着极为广泛的应用.目前比较常用的路径规划方法有网格法[1]、符号连通图法[2]、势场法等,这些方法计算实时性很强,便于机器人的动力学优化控制和实时路径规划,但不能保证找到全局最优路径.

事实上,在一些如建筑规划、城市交通的应用中,大多数障碍物可近似表示为简单多边形,这种情况下可以通过计算找到全局的最优路径.本文所讨论的优化标准为行走路线最短,工作Ξ收稿日期:2002-04-02

作者简介:易　晟(1975-),男,湖南醴陵人,中南大学硕士1