PAGE1
基于蚁群算法的机器人避障问题
摘要
机器人的开发与应用已成为当今学术界和工业界的研究热点之一。大部分机器人只能接受人类的指挥，或者运行预先编排好的程序，如何利用人工智能技术制定机器人的行动原则，一直是机器人应用领域的难题。本文采用了蚁群算法、局部优化模型等智能算法，对机器人在平面场景图中行走并躲避障碍物的问题进行了研究，得到了最短路径和最短时间路径的算法。
对于问题一，在寻找的最短路径时，由于可能遇到的障碍物较少，直接观察便不难看出最短路径只会出现一段圆弧，并能估计出这段圆弧可能出现的大致范围，关键便是确定出这一段圆弧的起点和终点。于是，我们以这段圆弧的起点和终点作为决策变量，以总长度最短为目标函数，构造了一个优化模型，用lingo软件运行，得到圆弧的起点为（70.50596，213.1406），终点为（70.60640，219.4066）。最终，我们计算出的最短路径长度为471.0372，路径详见表1。
在寻找、、的最短路径时，可能遇到的障碍物很多，路线很复杂。首先，我们将路线图简化为一个赋权网络图，并利用蚁群算法，找出了最短路径的大致路线。然后将这条路线分割为几段，每段路线只绕开一个障碍物。这样，我们就可以利用寻找的最短路径时同样的优化模型，求出每一段的最短路径，最后将每段最短路径求和，得出的最短路径为854.3759、的最短路径为1088.1951、的最短路径为2737.765，路径详见表2、表3、表4。
问题二需要寻找出的最短时间路径，我们将问题一中的优化模型做了修改，以总时间最短为目标函数，以圆弧的两个切点以及圆弧的半径为决策变量，用lingo软件运行，得到圆弧的两个切点为（）、（），半径为11.52688，最短时间为97.91781秒，路径详见表5。
关键词：人工智能；蚁群算法；优化模型；最短路径；机器人避障
问题重述
在一个800×800的平面场景图，在原点O(0,0)点处有一个机器人，它只能在该平面场景范围内活动。图中有12个不同形状的区域是机器人不能与之发生碰撞的障碍物。障碍物外指定一点为机器人要到达的目标点（要求目标点与障碍物的距离至少超过10个单位）。规定机器人的行走路径由直线段和圆弧组成，其中圆弧是机器人转弯路径。机器人不能折线转弯，转弯路径由与直线路径相切的一段圆弧组成，也可以由两个或多个相切的圆弧路径组成，但每个圆弧的半径最小为10个单位。为了不与障碍物发生碰撞，同时要求机器人行走线路与障碍物间的最近距离为10个单位，否则将发生碰撞，若碰撞发生，则机器人无法完成行走。场景图中4个点O(0,0)，A(300,300)，B(100,700)，C(700,640)。
机器人直线行走的最大速度为个单位/秒。机器人转弯时，最大转弯速度为，其中是转弯半径。如果超过该速度，机器人将发生侧翻，无法完成行走。
(1)机器人从O(0,0)出发，O→A、O→B、O→C和O→A→B→C→O的最短路径。
(2)机器人从O(0,0)出发，到达A的最短时间路径。
问题分析
问题一分析
1.问题一中第一个问要求定点按照一定的行走规则绕过障碍物到达目标点的最短路径，我们先可以包络线画出机器人行走的危险区域，这样的话，拐角处就是一个半径为10个单位的四分之一圆弧，通过那么然后采用拉绳子的方法寻找可能的最短路径（比如求O和A之间的最短路径，我们就可以连接O和A之间的一段绳子，以拐角处的圆弧为支撑拉紧，那么这段绳子的长度便是O到A的一条可能的最短路径），然后采用穷举法列出O到每个目标点的可能路径的最短路径，然后比较其大小便可得出O到目标点的最短路径。
2.第二问要求定点经过中间的若干点按照一定的规则绕过障碍物到达目标点后在回到，这使我们考虑就不仅仅是经过障碍物拐点的问题，也应该考虑经过路径中的目标点处转弯的问题，这时简单的线圆结构就不能解决这种问题，我们在拐点及途中目标点处都采用最小转弯半径的形式，也可以适当的变换拐点处的拐弯半径，使机器人能够沿直线通过途中的目标点，然后建立优化模型对这两种方案分别进行优化，最终求得最短路径。
问题二分析
问题二中要求定点按照一定的行走规则绕过障碍物到达目标点A的最短时间路径，我们先可以包络线画出机器人行走的危险区域，这样的话，拐角处就是以一个半径为10个单位的四分之一圆弧，通过那么然后采用拉绳子的方法寻找可能的最短时间路径，然后采用穷举法列出O到每个目标点的可能路径的最短时间路径，然后比较其行走时间长短得出O到目标点A的最短时间路径。
基本假设
1.假设机器人的自身宽度忽略不计。这样，机器人的运动可以看成是一个点的移动。
2.假设机器人直线行走和转弯时均以最大速度运行。
3.假设障碍物始终是题目所给的12个不同形状的区域，且位置，大小等性质一直不变。
符号说明