基于笛卡儿坐标系的迷宫路径规划算法

1、文章编号：（）软件时空基于笛卡儿坐标系的迷宫路径规划算法（四川大学）袁洁龚晓峰摘要：针对迷宫这类特殊的环境模型，提出了基于笛卡儿坐标系的新的路径规划算法。该算法通过找出机器人行驶方向和位置变化的关系，方便快捷地实现了对路径的记忆，并且在到达终点后能够通过一种简单的路径优化算法算出最短路径，最终实现以最短路径返回。此算法的可行性已通过轮式机器人实例得到证实。关键字：路径搜索；路径规划；笛卡儿坐标；机器人；迷宫中图分类号：文献标识码：，：，引言自从特别是嵌入式系统出现以来，轮式迷宫机器人和路径规划算法一直是许多先进国家作为培养训练计算机和控制类学生的两大重要课题。对迷宫机器人技术而言，路径规划的关

2、键就在于建立适当的环境模型。本文提出了一种将迷宫环境模型建立在笛卡儿坐标系上的路径规划算法。该算法的核心思想是：通过事先确定坐标系的原点和正方向，将迷宫环境中的点与笛卡儿坐标一一对应起来，以便于机器人进行各种环境信息的记忆和处理。本文首先从一个简单的迷宫模型着手，详细介绍了从环境建模，到路径记忆，再到路径优化完整实现过程。针对这种迷宫模型，我们已经研制出了相应的轮式机器人实例，实现了完整的路径规划。与传统迷宫机器人不同的是，在将迷宫环境映射到笛卡儿坐标的前提下，机器人可以更为简单灵活的对走过的路径进行规划和记忆。到达终点后，能够计算出从起点到终点的最短路径并按此路径返回，从而真正实现了机器人从

3、学习到记忆，从分析再到实践的一个完整的拟人化过程。最后本文还对更为复杂的迷宫环境进行深入的分析研究，从而将这种迷宫规划算法推向更宽的应用领域。感器获取。本设计属于后者，通过机器人不断的前行搜索，得到一个环境模型，再找出从起点到目标点的符合一定性能的可行或最优路径，它涉及的基本问题是环境模型的表达和搜索策略和优化方法。常用的基于传感器的路径规划方法主要有栅格法、人工势场法、遗传算法及模糊控制算法等。删格法主要思想是将机器人工作空间分为具有二值信息的网格单元，分别表示自由空间和障碍物，由此引导机器人找到可行路径。人工势场法是由提出的一种基于势场的方法。在机器人工作空间建立虚拟人工势场，目标点对机器

4、人产生引力，障碍物产生斥力，机器人在合力作用下找出可行路径。遗传算法是一种借鉴生物界自然选择和自然遗传机制的随机化的搜索算法。模糊控制算法则是把传感信息和目标模糊化，利用隶属度函数控制机器人运动。对于迷宫这类特殊的环境模型，这些方法都显得过于复杂而不适用。于是，我们试图寻找一种更为简单方便的环境建模方法来处理迷宫环境这类问题。技术创新路径规划技术概述路径规划技术是机器人研究领域中的一个重要分支。所谓机器人的最优路径规划问题，就是依据某个或某些优化准则（如工作代价最小、行走路线最短、行走时间最短等），在其工作空间中找到一条从起始状态到目标状态的能避开障碍物的最优路径。路径规划大体分为两种：一种是

5、基于模型的路径规划，作业环境的都是预知的；另一种是基于传感器信息的路径规划，作业环境全部未知，障碍物的尺寸、形状和位置信息必须通过传袁洁：硕士图设计中的环境模型邮局订阅号：元年技术应用例软件时空中文核心期刊微计算机信息（管控一体化）年第卷第期机器人行驶时，每遇到一个路口，就将当前坐标记下（，前面我们已经假设在设计中，路口间的距离都是一个删格）。的边长即单位长度，所以机器人经过的长度也都是单位，其变，只和当前行驶方向和上一个路口坐标（，）有关。化规律如下：表坐标变化与行驶方向的关系迷宫环境模型的建立迷宫环境主要有两个特点：一是路径主要是直线，二是路径大部分是垂直相交。针对这两个特点，我们用白纸和

6、黑线组成一个简单的机器人迷宫（图）。黑线有一定的宽度，并且相互垂直，作为机器人的导航线，代表机器人可以自由通过的安全路径。白纸代表环境中有障碍物的区域。首先将地图分解成相互连接的矩形栅格（如图虚线所示）。栅格不一定一样大，但要保证每一条安全路径都要在栅格边线上。我们始终假设起点是原点，起始方向为正方向，我们就可以把迷宫地图完全映射到一个笛卡儿直角坐标系上。我们把每个栅格边长定义为单位长度，把每个路径相交处和死胡同尽头定义为路口，这样，每个路口都对应一个整数坐标。如在上面的迷宫图中，起点坐标为（，），终点坐标为（，）。为了研究方便，我们还对迷宫进行了限制，要求我们的迷宫是树型迷宫。即迷宫中任意两

7、点只有唯一一条路径可以连通，即不存在回路。通过上表对机器人经过的路口坐标依次进行记录，就可以实现迷宫地图在内存上的映射。前面已经提到，迷宫搜索策略我们用的时左转优先法。现在就以图的迷宫模型为例，列出机器人前行时依次经过的坐标点。，当路径信息在内存中得到完整映射后，就需要一种算法让机器人知道回去的最短路径。我们是这样实现的：将机器人经过的坐标逐一进行比较，找出其中相同坐标，删去两相等坐标点中间的其他点，就得到的机器人返回时必须需经过的坐标点。该算法的物理意义就是屏蔽掉所走过的盲道，得到主干道。继续以上面迷宫模型为例，通过计算，得到主干道坐标点信息：迷宫搜索和路径规划技术创新迷宫的路径搜索迷宫的搜

8、索策略可以简单描述为：进入一路口，搜索并选择一路径往前走，若此路不通则返回选择另一未走过路径往前走，如此反复直至找到迷宫出口标志。实施这种搜索策略可以采路径编码法和固定的左转或固用三种方法：即直接地图映射法、定的右转法。对于这个树型迷宫，最常见的搜索法是固定左转法。即机器人遇到路口，始终向左转，如无左分支，则直走，如遇到的是死胡同，则原路返回直到遇到有左分支的路口。可以证明，这样最终可以走出迷宫或实现迷宫遍历。，按照前进时的逆运算，就可以通过坐标点求出每个路口的转弯情况。功能扩展前面介绍的设计实例，是笛卡儿坐标下的路径规划算法的一种简单的实现。但在现实生活中，我们遇到的迷宫模型要复杂的多（如图

9、）。路径的记忆和优化由于迷宫模型的路径都是直线，机器人当前位置只和它的上一个位置，当前行使方向以及行驶的单位长度有关。只需要记忆机器人当前行使的方向和经过的单位长度，就可以根据上一次的坐标计算出当前坐标。还是以我们的设计实例为例。为了表述简单，我们将轴正向称为东，再按上北下南左西右东的习惯，将东南西北四个方向分别与坐标轴方向对应。四个方向用两个位标志表示，定义如下：东：，南：，西：，北：每转一次弯，方机器人初始方向是东，即方向标志位为。向标志位发生相应的变化。其变化规律如图。当机器人左转时，其方向变化如外圈实线箭头所示；右转时，其方向变化如外圈虚线箭头所示；原地掉头时，方向变化如内圈箭头所示。

10、图复杂的迷宫地图这种迷宫的路径规划，难点之一在于路口坐标的确定。由于路径不是在规则的栅格的边上，路口间的距离不再只是单位长度，要对每个路口准确的定位，必须用更精确的表示方法。为了得到更为精确的坐标值，机器人必须具有测距功能。我们采取的方法是在车轮上均匀装上几个霍尔传感器，记录下车轮转动数和角度，测量机器人的行程，从而得到两路口间的距离，用表二来代替前面介绍的实例中的表，就可以按照图方向标志与小加转弯运动关系前面介绍的方法对这种较为复杂的迷宫环境进行路径规划。元年邮局订阅号：例表坐标变化与行驶方向的关系软件时空杨传华，杨萍，周美艳，刘金利自学习移动机器人在未知环境中的路径规划，（）：于红斌，李孝

11、安基于删格法的机器人快速路径规划微电子学与计算机，（）：庄慧忠，杜树新，吴铁军机器人路径规划及相关算法研究科技通报（）李强，林良明，颜国正基于进化的移动机器人路径规划方法式（）这种迷宫路径规划，还有个难点是在进行路径优化时，如何识别相同的路口。因为受测距误差和转弯时位移等因素的影响，同一坐标在多次经过时不可能得到完全相同的坐标。在坐标比较时，我们引入一个误差系数，当时，就认为这两个坐标是同一坐标。的大小关系着路径优化的正确与否。的值和迷宫的复杂程度和误差大小有关，可以在程序中实现设置好，也可以路径探索时通过模糊算法计算得出。这种方法，已经通过仿真和试验得以证实。另外，可以证明，只要迷宫起点没有

12、设置在回路内，机器人用固定左转法是不会在回路中循环的。但若机器人的起点设在回路以内，就极有可能陷入死循环。针对这种问题，我们用一个转弯计数器记录转弯情况。该计数器初值是，每左转一次计数器加，右转一次减，当计数器绝对值大于时，说明进入循环，机器人改变路径搜索方式，改用固定右转法搜索。通过仿真，已经证明这种方法的可行性。：，：作者简介：袁洁，女（），汉，四川乐山人，硕士，研究方向：检测技术与自动化装置；龚晓峰：男（），汉，浙江金华人，副教授，博士，研究方向：计算机控制与管理：（），（），；（）（），（四川成都四川大学电气信息学院）袁洁龚晓峰（，）小结本文以一个简单的迷宫模型为例，提出了一种将迷宫环

13、境模型建立在笛卡儿坐标系上的方法。基于笛卡儿坐标建立的环境模型，只需要确定原点和轴正方向，就可以唯一确定迷宫中每个点的坐标。这种方法描述简单，理解容易，而且大大简化了路径的记忆过程和优化过程。由于我们研究的对象是迷宫，此算法适用的环境模型必须满足两个前提：路径都是直线，相交都成直角。这两个前提在一定程度上限制了算法的运用范围，在更复杂的机器人工作环境下，需要对此算法作更多的改进。但是，在现实生活中，大多数建筑、公路以及人造轨道基本都是直线型且垂直相交的。因此，这种基于笛卡儿坐标系的路径规划算法，无论在教学还是在实际生活中都有很高的研究价值。本文作者创新点：迷宫具有以下两个突出特征：安全路径都是

14、直线，路径相交成直角。针对类似这样的环境模型，提出了一种新路径规划方法，即把环境映射到一个笛卡儿坐标上，用坐标值表示环境中的节点。这样大大简化了机器人路径记忆的难度，同时又为路径优化提供了很大的方便。只需要比较走过的路径，找出其中重复的节点，屏蔽掉相同节点间的路径，即可得到从起点到终点的最短路径。这种路径规划算法思想简单，易于实现，且扩展性强，可广泛应用于现代建筑、公路及轨道的机器人路径规划中，有很大的实用价值。通讯地址：（四川四川省成都市四川大学电气信息学院研）袁洁（收稿日期：）（修稿日期：）技术创新（上接第页）董辉，信号处理滤波器设计基于和朱义胜，北京，电子工业出版社，作者简介：汤宁生（），男（汉族），安徽滁州人，电子科技大学自动化工程学院，检测与自动化装置（专业），硕士研究生，主要从事数据采集和混合滤波器组研究；黄建国，男，电子科技大学教授，从事电子测量、系统集成等方面的科研工作；王志刚，男，电子科技大学高级工程师，主