|
|
机器人的行走问题是现今比较流行的一个课题，它主要是针对机器人在行走过程中的路径规划和对周围事物的处理、避障等问题。在此领域的应用实例有巡逻机器人，自动扫地机器人，灭火机器人，导购机器人等。
本毕业设计通过学习图的最短路径算法，然后在Microsoft Windows XP操作系统下，采用Microsoft Visual Studio .NET 2003编程软件作为开发工具，c++为开发语言来开发设计实现了导购机器人程序。通过检测，本程序符合设计要求，能满足用户的需求。
关键词 导购机器人、最短路径算法、C
超市导购机器人行走路线规划具体步骤如下：
环境为由大尺度简单多边形障碍物构成的平面场景．在该工作环境中，由于障碍物尺度较移动车大得多，可将移动车退化为一个质点考虑。路径规划可表述为：在一个平面中顺序给定数个多边形顶点的坐标及起点和终点，求从起点到终点且与各多边形不相交的最短路径。
第一步：把整个环境分成若干个简单的区域块。环境的组成相对复杂，如障碍物，货架，墙壁，门，楼梯，人等。通过对各种环境因素进行分类分割成一个个的实区域或虚区域。
第二步：处理区域间的连通性。1）对虚区域进行归类，并且去除可去除的虚区域。2）对于一些相互不联通的区域进行差补操作。3）优化之前处理的结果，使路线最短。
第三步：选择最短路径，行走到目的地点。
其中路径选择的算法概述如下：
Stepl：多边形预处理。先去除两邻接边在同一直线上的顶点，然后调整多边形的顶点，使其顶点按顺时针方向顺序排列。
Step2：根据已知的各多边形的序列顶点及起点和终点产生图G=(V，E)，V= E={ }．V为包含各多边形的顶点、起点和终点的点集，E为V中任意两点连接形成的边集．然后标记V中除起点和终点外其余各点的凸凹性和各多边形 的凸凹性。
Step3：计算E中各边的权值，E各边的权值集合表示为D．如果边合法且边两端点同为 非凹点则此边的权值为边的长度，否则其权值为+∞．边合法是指能从边的一个端点“看到” 边的另一端点。
step4：由G及D用Dijkstra算法计算出起点到终点的最短路径。
