通用自主机器人相对区域地图信息导航系统.doc

通用自主机器人相对区域地图信息导航系统上海卢湾高级中学 董忍仁 张倬 指导老师：张晓骏关键字（Key Words）：智能机器人 相对区域地图信息 自主推测导航摘要本文通过对自主机器人导航算法的分析探索，提出了相对区域地图信息的概念。并以此结合多种信息进行自主推测导航。在此基础上实现自主环境定位和路程的自主规划。这套算法是模拟了人的思维模式和行为特征，具有较强的智能性、通用性和灵活性，并有较大的发展潜力。前言机器人自主导航一直是颇受关注的课题，特别是智能化的自主导航也并没有达到成熟的程度。在对几个智能机器人成功先例的研究过程中我们发现,在大多数需要移动的智能机器人任务中,大多都可以事先得到十分精确地图，或相关的信息。如何合理利用这些信息，在机器人执行任务之前，事先进行周密规划，或在执行动态任务中进行动态的实时的规划。成为了智能化自主导航的关键。相对区域地图信息的表示对地图信息的识别是自主机器人行为的前提，而其中又有精确识别和模糊识别之分，为了使机器人能更接近地模拟人的思维模式，我们提出了相对区域地图的概念。l 相对区域的概念相对区域地图中，首先要涉及到的是区域的划分。对于地图的识别，机器人多以坐标定位为主，像GPS导航就是一个很好的例子，我们统称为精确识别。而人面对一张复杂的地图，则原理与此截然不同。人所认知的不是精确的坐标值，而是一个相对的抽象信息：比如说，从A地向正南方向沿B马路将与C马路十字相交、然后在下一个丁字路口左拐至D马路最后抵达E地。这个，我们称之为相对识别。在这其中ABCDE这些个地域是有其固定特征的抽象概念，而且它们在地图中的位置是连续相对的。所以，我们把“在一个固定地理环境中，具有与其他地域相对的、连续的位置不同特征的抽象地域概念”称为相对区域，在本文中简称区域。l 相对区域地图的编码单独的相对区域是没有任何意义的，只有把它们有机的组织起来，表述区域之间的相对联系，才能够具有完整的意义。这便形成了相对区域地图。我们以智能机器人灭火比赛的场地为例，表述一下相对区域地图编码的规则。为了便于研究，我们对日常的地理信息做出了简化处理：（事实上无论用何种方式表示，只要可以表示区域间的差异即可）1、我们把方向简化为4个直角方向；2、我们把地域特征仅表示为每一方向的有无障碍，即墙体的有无。 图一：灭火场地的区域划分区域的划分可见图2， 地图中所有的区域它们的位置特征不仅是相对的，而且是连续的，这些区域就是智能导航的基础。我们把0作为一个空区域即初始值来处理。每一个区域的编号必须是唯一、不重复的，且数序与相对位置等地域特征无关。图中的区域号可以随机指定。为了讨论方便，我们暂把图2的区域作如上编号，实际应用中序号完全可以由机器人随机产生。l 相对区域模型的建立建立合理、正确的区域信息模型是实现自主推测导航的关键。我们利用面向对象的程序设计（OOP）思想来建立这一模型。因为，这样可以大大简化区域间的操作，特别在在路程生成时尤为突出。在C+中建立一个“相对区域”的类，Class Carea。简略定义如下：Class Careapublic:Int get_ir(); /获取四周障碍信息，Int* coordinates();/获取区域坐标，用一维四列数组表示Carea* get_next(int n);/获取指定方向的相连区域号Carea* get_before();/自主路径搜索时经过的前一区域private:int coordinates4;/区域坐标int ir;/障碍信息int num;/区域号Carea* next4;/四周相连区域其中，核心是四周相连区域的表示和障碍信息，而其他则主要在自主路程生成时用到。自身区域号0方向区域号1方向区域号3方向区域号2方向区域号首先要确定一个始方向 即0方向，然后依顺时针为1方向、2方向、3方向（见图3）。这个方向对应nexti中的索引值。以图2中的11号区域为例，设正上方为的始方向(即0方向)，相连区域信息为：next0=0(墙)、next1=10号区域的指针、next2=0(墙)、next3=12号区域的指针。障碍信息实际是相连区域信息的简化表现形式，直接表示接受到的传感器信息。如遇到有效的相连区域就以0表示，即此方向上无障碍；如遇墙壁就用1表示，即有障碍。用一个整形变量表示，int ir。高位到低位对应顺时针方向。11号区域的障碍信息表示为：0b1010。图三：相连区域信息int num记录区域号。另外，还用int coordinates4来表示区域的矩形坐标定位。使其的适用范围更广。我们用Class Carea类定义了一个对象数组Carea MyArea16来表示不同的区域，从而在计算机内建立一个图的模型，图中的每个元素就是现实中的每个区域，同时这也是一个带权的有向图。但是在连接时我们却使用了双向的链接，这样在下面的遍历过程中就可以避免使用递归算法，因为递归将消耗巨大的系统资源和系统时间，而当地图趋向复杂时这一矛盾就显的尤为突出了。 路程信息的表示光有了一张地图还不行，必须还要有与你的起始地和目的地相符合的路程信息。我们这里的路程其实包括：路径信息、动作信息。l 路径信息路径信息就是区域号的有序排列，它表示的是你先后通过的区域。当然前后之间的区域必须是相连接的。其作用就相当与在地图上画一条行进线路。路径可以人为指定，但这显然大大抑制了机器人的灵活性和通用性，特别是在复杂环境中。在实际使用中，我们只需告诉机器人一个起始区域和一个目的区域（或其特征）。相应的路径就会由机器人自己生成。l 动作信息有了合适的地图和正确的线路，人已经可以轻松的完成任务，而机器人依然举步维艰。因为，人在由一个区域进入下一个区域时，会实时地做出合适的动作，如前进、左转等。机器人则不具备直接的能力。因此，除了路径信息外，在路程信息中还应包括在区域间运动时相应的动作信息。动作信息可以像人一样实时生成，也可以根据路径预先生成。效果应是一样的。考虑到速度和程序结构等因素，我们使用的是预先生成，并与路径信息组合在一起，构成路程信息。动作信息是根据路径信息和机器人所执行的任务而生成的。他取决于路径上的两个相邻区域的位置关系、机器人运动的方向及在该区域所要完成的任务。在我们试验的灭火机器人项目作了如下的动作定义：0 停止，1直行，2后退，3 左转，4 右转，5 左后转，6 右后转，7 灭火，8 不改变运行状态。l 路程信息的表示例如，在图2中，机器人由10出发经11、12左拐至13。我们需要表示的就是10-11直行，11-12直行，12-13左拐这样一种信息。于是，在实验中我们就用一个二维数组来表示一条路程。每一行表示一个路程中的区域和由上一区域进入该区域时的动作信息。如下： 区域号|动作int route2,4=10,1,11,1,12,2,13,1;第一列表示区域号。所有的第一列由前到后就使路径信息。第二列就是动作信息。数值对应上文的定义。路径和行动的自主规划l 机器人的自动定位虽然我们知道详细的地图信息，但是我们并不可能就此推断出机器人的确切位置。因为在实际情况中，拥有相同，或相似特征的区域可能不止一个，无法用一些简单的传感器来进行绝对定位 ，如果利用一些复杂的传感器则需考虑到成本，体积等多方面的因素。我们的思路是将这种不明显的特征扩大，从而分辨其中的区别。例如，当你在一个陌生的城市中迷路，手中只有一份地图，不巧你所在的路，在地图中名字相同的路可能有好几个。你不知道你在哪一个，你可能会任意向前或向后走，再看看前面名字相同的几条路有哪条附近是这条路，如果只有一条，那么你就找到你的位置了。在程序中也可以这样做。即在发现传感器读入的数值并非是区域中唯一的，即可生成一个列表，记录拥有相同或相似特征的区域，然后在下一区域中删除列表中下一区域不符合的记录。直到只有一个记录为止。这样就可以确定机器人的确切位置。l 路径的自动生成在确定自身的位置和目标位置之后,当务之急就是建立一条从自身位置到目标位置的最佳路线，以供机器人执行。因为如果让机器人本身进行搜索是没有意义的，同时也可能大大浪费时间，并降低可靠性。所以我们就在程序内部建立一个模型，用来模拟机器人的搜索过程，利用面向对程序设计（OOP）优点，我们建立了一个机器人模型（即程序内部的类），和一个区域模型。并尽可能详细的描述它。如：机器人有方向，光敏，热敏等环境参数，位置可用一个指向区域类的的指针表示，我们设为Carea * here。在建立了一个机器对象，和一个区域类的对象数组之后，就是要建立区域与区域之间的相对关系,在程序内部主要由指针和地址组成的图结构来表示，列如在机器人灭火比赛转化为图结构是这样的： 图四：区域路径的图结构如果我们假设起始地址为1号区域，我们的搜索方式是这样的，首先读取起始地的信息，（这一点有点象递归遍历中的前续遍历。）在与其特征对比之后，若不是1号区域则可根据前面所说的相对区域定位的方向重新定位。若是1号区域，则默认将1号区域下一个区域的地址赋给机器人的here属性，即将机器人行驶到2号区域，并将1即1号区域的区域号写入一个空的数组。作为路径信息。在8号区域机器人将有两个区域地址可供选择，我们先默认选择其中的第一个，向10号区域前进，当到11号区域时，会发现无路可走，则可用这个区域的before地址（上面我们说过，在链接时我们用的是双向链表结构，也就是可以返回的），向回走，当退回到8号区域又会发现，有两条路可走，一条走过一条没走过，则选择一条没走过的，就前进，直到区域特征与目标区域的特征相同为止，由此，我们可得到一个经过区域的数组。l 路径的优化通过自动路径的生成我们可以生成一条从自身位置到目标位置的路径，但是这种路径并非是最佳的。这就需要对路径进行必要的优化，使之成为最佳路径。例如，在从上图中的1号区域到9号区域的生成的路径可能是这样的way =1，2，4，7，8，10，11，10，8，9 实际上模拟机器人在8号至11号区域走了一段歪路,这时我们就可直接在数组中将第一个8至第二个8之间的区域直接删除,并同时删除其中一个8,这样就可以很简单的删除这一段歪路,在真正的机器人执行时将不会走这条路,同时我们也考虑到另一种情况。 在这种情况中无论是1，2，4，7，8，9和1，3，5，6，9能到达9号区域,可能我们默认的从1号区域开始按前一种走法走,即向2号区域走,这样虽然也可以到达9号区域 ,但不是最佳路线,我们的方法是在路径生成和完成第一步优化工作之后,描述每一条没有走过的路(我们在每个区域对象中有专门的变量记录每条路是否走过),实际上在扫描1号区域时会发现1号到3号的区域没有走过,于是沿3号区域走到9号区域之后，比较原有数组会发现原来的路径中也有9号区域。比较两段路径的长短（从1号到9号）然后用短的覆盖长的。（在实验中我们比较的是区域数，因为我们默认每个区域的长度相同，但在实际情况中比较两段路径中区域的长度之和更科学一些。）l 动作信息的生成这一步算法并不难，但没有它机器人则寸步难行。如果在路径信息中，要从11号区域到12号区域，如12号区域在11号区域的前方，则执行向前进；如12号区域在11号区域的左侧，则执行向左传。依次类推。最后与相对应的路径信息统一起来，共同生成完整的路程信息。l 执行操作有了具体的路程自主规划后的路程信息和路径信息，我们就可以通过它们在运行中实现自主推测导航。首先，我们判断是否到达目的区域，也就是表示区域号的变量是否大于最大区域号。当为否时则更新当前区域路程信息，也就是更新表示区域信息的对象数组和路程信息数组的索引号。从路程信息中读取当前要执行的动作并执行，然后判断是否满足下一个区域信息，也就是是否到了下一个区域。满足了就循环到开头。这样直到进入最后一个区域，完成任务为止。实际应用在试验和文章中我们都是使用了机器人灭火比赛的场地进行分析的，但是在实际的应用这样简单的任务是毫无意义的。因为在实际情况中要比在灭火场地复杂的多。l 复杂地理环境下的区域导航在复杂的地理环境下，要能正确的导航，添加一些必要的传感器是必要的。同时信息也不象在灭火比赛中那样简单，有时常常是一张图片。这就需要一定的图形分析模块，和匹配模块，来代替简单的对比。现在我们那当年火星探路者号在火星的任务为例，在图片上我们已经标好了区域号。根据图论的基本知识，在图形分析时我们可以很简单的根据灰度来判断图中那些石头时机器人可以越过的，那些则是很难越过的。我们发现第22，41，15，16，25，26对于机器人来说可能很难越过，于是在生成图的时候（这里可能是一个稀疏距阵），就不会有这些区域的元素。这次的任务可能是要到17号区域取一块岩石。这样根据上述所说的方法就不难找出图中用红线划出的那条路径。在具体执行的过程中，理论上可能不再需要传感器，但事实上，由于误差的存在，这是很难做到的。这就需要对机器人上的传感器返回值进行复反馈控制。l 巨型地图的规划在实际的情况当中，可能还会遇到这种情况，比如，需要从上海的一点，运动到北京的一个指定位置。虽然我们知道详细的地图信息，但是要完全处理从上海到北京的所有信息的工作量将非常惊人，有时几乎是不可能的。但是在相对区域的概念中一个区域有时可以是一块很大的地区，也可以是许多小区域的合集。这样我们就可以把上海看成是一个区域，北京看成一个区域，中国看成是一个大的地图，先找出从上海到北京的路径，再分析怎么出上海，和怎么进北京。这样可以大大简化程序的复杂度。l 不明显的特征区域或非地理特征区域在很多地方区域并不是十分明显的，有是也可能是非地理特征的，如图：比如在一个空旷的平地上，发生火灾，在图中红色的深浅表示温度的高低。要靠平地与平地之间微小差异来判断区域地位置是十分困难的。这时温度的传感器也可以作为判断区域位置的标志，但