下载文档原格式
v1.0 可编辑可修改机器人避障问题的解题分析摘要：本文对2012年全国大学生数学建模竞赛D题机器人避障问题进行了全面分析，对最短路的设计进行了理论分析和证明，建立了机器人避障最短路径的几何模型，对最短时间路径问题通过建立非线性规划模型，有效地解决了转弯半径、圆弧圆心位置和行走时间等问题。
关键词：机器人避障；最短路径；Dijkstra算法；几何模型；非线性规划模型1 引言随着科学技术的进步和计算机技术的发展，机器人的应用越来越广泛，在机器人的应用中如何使机器人在其工作范围内为完成一项特定的任务寻找一条安全高效的行走路径，是人工智能领域的一个重要问题。
本文主要针对在一个场景中的各种静态障碍物，研究机器人绕过障碍物到达指定目的地的最短路径问题和最短时间问题。
本文以2012年“高教社”杯全国大学生数学建模竞赛D题“机器人避障问题”为例进行研究。
假设机器人的工作范围为800×800的平面正方形区域（如图1），其中有12个不同形状的静态障碍物，障碍物的数学描述（如表1）：图1 800×800平面场景图表1在原点O(0, 0)点处有一个机器人，它只能在该平面场景范围内活动，机器人不能与障碍物发生碰撞，障碍物外指定一点为机器人要到达的目标点。
规定机器人的行走路径由直线段和圆弧组成，其中圆弧是机器人转弯路径。
机器人不能折线转弯，转弯路径由与直线路径相切的一段圆弧组成，也可以由两个或多个相切的圆弧路径组成，但每个圆弧的半径最小为10个单位。
为了不与障碍物发生碰撞，同时要求机器人行走线路与障碍物间的最近距离为10个单位，否则将发生碰撞，若碰撞发生，则机器人无法完成行走。
机器人直线行走的最大速度为50=v 个单位/秒。
机器人转弯时，最大转弯速度为21.0100e1)(ρρ-+==v v v （ρ是转弯半径）。
如果超过该速度，机器人将发生侧翻，无法完成行走。
场景图中有4个目标点O(0, 0)，A(300, 300)，B(100, 700)，C(700, 640)，下面我们将研究机器人从O(0, 0)出发，求O→A、O→B、O→C和O→A→B→C→O的最短路径，以及机器人从O(0, 0)出发，到达A的最短时间路径问题。
机器人自主导航技术的路径规划和避障策略机器人自主导航是指机器人能够在无人干预的情况下，根据外部环境和自身感知信息，自主地决策和规划路径，以达到预定目标的能力。
路径规划和避障是机器人自主导航中两个重要的技术环节，下面将对这两个方面的技术进行全面的介绍和探讨。
路径规划是指机器人通过一系列算法和决策机制，在环境中找到一条最优或次优的路径，以达到目标点。
路径规划主要有两种方法，一种是基于图算法的方法，另一种是基于采样的方法。
基于图算法的路径规划方法主要有最短路径算法和搜索算法。
其中最常使用的最短路径算法是A*算法和Dijkstra算法。
A*算法是一种适用于有向图的寻路算法，通过综合考虑启发式评估函数和实际路程代价，能够在保证最佳路径的同时，有效地减少搜索空间。
Dijkstra算法则主要用于无向图的单源最短路径求解，通过不断更新路径的距离估计值，可以找到起点到各个顶点的最短路径。
这两种算法结合启发式评估函数等方法，可以在复杂的环境中高效地规划路径。
另一种基于采样的路径规划方法是通过对环境进行采样，然后利用采样数据进行路径搜索。
常见的算法有RRT算法和PRM算法。
RRT算法通过随机采样和迭代生成一棵树形结构，再根据目标点进行路径搜索。
PRM算法则是先进行采样，然后建立一个具有连接关系的节点集合，最后根据环境中的障碍物信息进行检查和优化。
这两种采样算法具有较强的鲁棒性和适应性，对于不确定的环境可以依然能够找到一条较为合适的路径。
除了路径规划，避障也是机器人导航中一个非常关键的环节。
机器人在移动过程中需要不断对周围环境进行感知，以避免碰撞和采取必要的规避动作。
避障主要有两种策略：基于传感器的避障和基于模型的避障。
基于传感器的避障策略是依靠机器人的传感器获取周围环境的信息，并基于这些信息做出避障决策。
常用的传感器有激光雷达、摄像头、超声波传感器等。
激光雷达可以通过扫描环境，获取障碍物的距离和形状信息，从而判断机器人行进的安全路径。
机器人避障问题Company Document number：WTUT-WT88Y-W8BBGB-BWYTT-19998机器人避障问题摘要本文研究了在一个800800⨯平面场景里，机器人通过直线和圆弧转弯，绕过障碍物，到达目标点的问题，解决了到达目标点路径最短，以及到达A 点时间最短的问题。
文章将路径划分为若干个这种线圆结构来求解。
对于途中经过节点的再到达目标点的状况，我们采用了在拐点和节点最小转弯半径的形式.问题一，将其分解成圆线结构进行求解，利用枚举法将最短路径表示出来，结果是：O A →的距离是O →B 的距离是O →C 的距离是O →A →B →C →O关键词：最短路径 最短时间 几何应用 最优化问题一 问题重述机器人从指定点到达的目标点，其行走路径由直线段和圆弧组成。
机器人转弯路径由与直线路径相切的一段圆弧组成，也可以由两个或多个相切的圆弧路径组成，但每个圆弧的半径最小为10个单位。
同时要求机器人行走线路与障碍物间的最近距离为10个单位，机器人直线行走的最大速度为50=v 个单位/秒。
机器人转弯时，最大转弯速度为21.0100e 1)(ρρ-+==v v v ，其中ρ是转弯半径。
要求建立机器人从区域中一点到达另一点的避障最短路径和最短时间路径的数学模型。
对场景图中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.问题一要求从起始点o 绕过障碍物到达目标点，并且与障碍物最小距离为10，拐弯半径越小，走的路线越接近直线，在拐弯处画一个以拐点为圆心，半径为10的圆，这样我们就可以从起始点出发，分别做圆的切线，直到终点。
机器人路径规划与避障技术研究近年来，随着科技的飞速发展，人工智能在各个领域都得到了广泛的应用。
机器人作为人工智能的代表之一，其在工业生产、医疗服务、物流配送等方面发挥着越来越重要的作用。
对于机器人来说，路径规划与避障技术是至关重要的，它直接关系着机器人的运动效率和运动安全。
本文将探讨机器人路径规划与避障技术的研究和应用。
一、路径规划的重要性机器人在执行任务时，需要根据任务要求和环境条件，规划出一条合适的路径，以实现高效且安全地达到目标点。
路径规划是机器人导航中的核心问题，其目的是使机器人从起始点到达目标点，期间经过的路径是最优的。
最优路径可以指最短路径、最少耗时路径、最低能耗路径等。
机器人路径规划需要考虑到环境约束、机器人自身能力以及任务要求等因素。
环境约束包括静态约束和动态约束，静态约束是指一些不可通过的区域或障碍物，而动态约束则是指一些随时间变化的约束，例如人群的分布变化。
机器人自身能力则包括感知能力、定位能力、决策能力和动作能力等。
而任务要求则基于具体任务而定，例如送餐机器人需要将食物准确送到指定地点。
二、路径规划的方法路径规划的方法有多种，常见的方法包括图搜索、模拟退火算法、遗传算法、蚁群算法和A*算法等。
这些方法各有优劣，可以根据具体情况选择合适的方法。
图搜索算法是一种基于图的搜索方法，其中最著名的算法是Dijkstra算法和A*算法。
Dijkstra算法用于无权图的最短路径搜索，它通过从起始点开始，逐步扩展搜索范围，直到找到目标点为止。
而A*算法则是在Dijkstra算法的基础上引入了启发式函数，能够更加高效地搜索最优路径。
模拟退火算法是一种随机搜索算法，它模拟金属退火的过程，通过接受一定概率的不优解来避免陷入局部最优解。
遗传算法则是根据生物进化的原理，将优良个体通过交叉和变异操作生成新的个体，以求得最优解。
蚁群算法则是模拟蚂蚁觅食行为的优化算法，蚂蚁在搜索过程中通过留下信息素来引导其他蚂蚁找到最优路径。
机器人技术中的路径规划与避障策略研究路径规划与避障策略是机器人技术中非常重要的研究领域。
在机器人的自主导航和智能行动中，能够准确规划路径并避免障碍物的能力至关重要。
本文将探讨机器人路径规划与避障策略研究的发展现状、相关技术方法和应用场景。
一、发展现状随着科技的不断进步和人工智能的快速发展，机器人技术在各个领域中得到了广泛应用。
路径规划与避障策略作为机器人技术的基础，也取得了显著的进展。
目前的研究主要集中在以下几个方面：1. 传统路径规划算法传统路径规划算法广泛应用于机器人导航中，如最短路径算法、A*算法和迪杰斯特拉算法。
这些算法可以通过建立地图，并利用图论中的相关算法，计算出到达目标点的最优路径。
2. 全局路径规划全局路径规划是指在考虑机器人周围环境的情况下，规划出一条从初始位置到目标位置的路径。
常用的方法有基于图搜索的方法和基于采样的方法。
前者通过搜索算法（如A*算法）在已知地图上进行路径规划，而后者则通过随机采样来寻找可行路径。
3. 局部路径规划局部路径规划是指机器人在行进过程中对遇到的障碍物进行实时避障。
常用的方法有基于激光雷达的方法和基于视觉感知的方法。
前者通过激光雷达获取周围障碍物的信息，并采用避障算法（如人工势场法）进行实时规避；后者则利用计算机视觉技术对周围环境进行感知，进而进行避障决策。
二、相关技术方法为了实现机器人的路径规划与避障，研究者们提出了许多相关的技术方法。
以下是一些常用的技术方法：1. 人工势场法人工势场法是一种广泛应用于机器人避障中的方法。
它通过在环境中构建势场，将机器人视为一个带电粒子，利用电磁力的作用使机器人避开障碍物。
该方法简单高效，但存在局部最小值和振荡等问题。
2. 蚁群算法蚁群算法源于对蚁群觅食行为的仿真，可以用于路径规划和避障。
通过模拟蚂蚁的觅食行为，通过信息素的传递和蒸发，在搜索空间中寻找最优路径。
蚁群算法具有优秀的全局搜索能力，但也存在收敛速度慢的问题。
机器人的避障与路径规划技术研究机器人的避障与路径规划技术在现代智能系统中起着至关重要的作用。
随着人工智能技术的不断发展和应用领域的扩大，对机器人的智能化要求也越来越高。
在日常生活中，我们可以看到越来越多的智能机器人被应用于各种场景，如无人驾驶汽车、智能家居、物流配送等。
而这些应用都需要机器人具备避障与路径规划的能力，以确保其能够安全、高效地完成各项任务。
机器人的避障技术是指机器人在行进过程中遇到障碍物时，能够通过感知、判断和控制等方式避开障碍物，确保行进路径的畅通。
目前，主流的机器人避障技术主要包括基于激光雷达、摄像头、超声波传感器等多传感器融合的方法。
这些传感器可以获取机器人周围环境的信息，如障碍物的位置、大小、形状等，从而为机器人的避障行为提供数据支持。
在避障过程中，机器人通常会通过路径规划算法来确定避开障碍物的最佳路径，并通过控制算法来实现路径跟踪，使机器人能够安全地绕过障碍物并继续前行。
除了基于传感器信息的避障技术外，还有一些基于深度学习和强化学习的避障方法逐渐得到关注。
深度学习技术可以通过大量的数据训练神经网络模型，使机器人能够自动学习并优化避障策略。
而强化学习则可以通过奖惩机制引导机器人不断尝试，最终找到最优的避障策略。
这些新兴的避障技术为机器人的智能化发展提供了新的思路和方法。
路径规划是机器人在避开障碍物后，确定前进路径的过程。
在复杂环境下，机器人需要考虑不仅仅是避开障碍物，还需要考虑全局路径规划，以最短的路径达到目标点。
目前，常用的路径规划算法有A*算法、Dijkstra 算法、RRT算法等。
这些算法在不同场景下有各自的优势和适用性，可以根据具体任务需求选择合适的算法进行路径规划。
除了传统的路径规划算法外，近年来还出现了一些基于机器学习的路径规划方法。
例如，基于深度强化学习的路径规划方法可以通过模拟环境和奖惩机制来训练机器人学习最优路径规划策略。
这种方法可以适应不同环境和任务的需求，具有很强的通用性和灵活性。
机器人路径规划与避障技术优化研究近年来，智能机器人技术日新月异，越来越多的行业开始应用机器人自动化生产，这提高了生产效率和品质，降低了生产成本。
机器人的核心技术之一就是路径规划，即使是在简单的环境中，机器人都需要规划一条最优路径，以此保证在运动过程中不会与周围环境碰撞。
本文将重点探讨机器人路径规划与避障技术的优化研究。
一、机器人路径规划路径规划是机器人行动的核心，它决定了机器人如何在世界中移动。
路径规划技术通常可以分为全局路径规划和局部路径规划两种。
1、全局路径规划全局路径规划指的是机器人在环境中移动时需要规划一条从起点到目标点的最短路径。
该路径规划需要根据机器人所在的环境建立一张地图，使用搜索算法，如A*算法等，在地图上搜索出最短路径。
全局路径规划需要考虑到避障问题，并且需要求解一条最短路径，因此在大规模的环境中全局路径规划会耗费大量的计算资源，而且算法运行时间会变得非常长，这也会影响到机器人的实时性。
2、局部路径规划局部路径规划是指机器人在行动过程中需要根据所处环境中的障碍物实时调整路径。
局部路径规划通常采用基于反应式神经网络(RNN)的方法进行实现。
在图像与传感器数据输入后，RNN算法会在快速而准确地计算机器人碰撞情况的同时，实时修正机器人的移动方向。
二、机器人避障技术随着智能机器人技术的不断发展，机器人的应用场景越来越复杂多样，不同的应用场景对于机器人的避障能力提出了更高的要求。
机器人避障技术根据应用场景可以分为三种类型：静态避障、动态避障和混合避障。
1、静态避障静态避障指机器人需要在静态环境下躲避固定障碍物。
通常，机器人所有的障碍物都会被建立在地图上，全局路径规划算法可以端博地找到可以到达目标的最短路径，而局部路径规划则可以在实时监测到机器人周围的障碍物后对路径进行微调。
2、动态避障动态避障指避免机器人与移动物体碰撞。
与静态避障不同，动态避障需要考虑时间因素。
这种情况下，机器人不能简单地建立地图来规划全球路径，在规划路径的同时，机器人需要不断检查和更新环境的动态变化。
D题机器人避障问题摘要本文综合运用分析法、图论方法、非线性规划方法，讨论了机器人避障最短路径和最短时间路径求解问题。
针对问题一，首先，通过分析，建立了靠近障碍物顶点处转弯得到的路径最短、转弯时圆弧的半径最小时和转弯圆弧的圆心为障碍物的顶点时路径最短、转弯在中间目标点附近时，中间目标点位于弧段中点有最短路径的三个原理，基于三个原理，其次对模型进行变换，对障碍物进行加工，扩充为符合条件的新的区域并在转弯处圆角化构成障碍图，并通过扩充的跨立实验，得到切线和圆弧是否在可避障区的算法，第三，计算起点、中间目标点和最终目标点和各圆弧及圆弧之间的所有可避障切线和圆弧路径，最后给这些定点赋一个等于切线长度或弧度的权值构成一个网络图，然后利用Dijkstra算法求出了O-A、O-B，O-C的最短路径为O-A：471.0372个单位，O-B：853.7001个单位，O-C：1086.0677个单位；对于需要经中间目标点的路径，可运用启发规则分别以相邻的目标点作为起点和终点计算，确定路径的大致情况，在进一步调整可得到O-A-B-C-O的最短路径为2748.699个单位。
针对问题二，主要研究的是由出发点到达目标点A点的最短时间路径，我们在第一问的基础上考虑路径尽可能短且圆弧转弯时的圆弧尽量靠近障碍物的顶点，即确定了圆弧半径最小时的圆弧内切于要确定的圆弧时存在最小时间路径，建立以总时间最短为目标函数，采用非线性规划模型通过Matlab编程求解出最短时间路径为最短时间路程为472.4822个单位，其中圆弧的圆心坐标为(81.430,209.41)，最短时间为94.3332秒。
圆弧两切点的坐标分别为（70.88,212.92）、（77.66,219.87）。
关键字：Dijkstra算法跨立实验分析法非线性规划模型一.问题的重述图是一个800×800的平面场景图，在原点O(0, 0)点处有一个机器人，它只能在该平面场景范围内活动。
机器人避障问题摘 要本文讨论的是机器人避障问题，运用改良的橡皮筋算法思想，对最优路径逐步探索，并进行了大胆猜想．通过分析，利用几何关系证明了猜想的正确性，以此得到判断最短路径的三个原则：一、所走路线应尽可能接近两目标点与目的地连线；二、目标点转弯半径越小越好；三、找不到两圆间的公切线时，机器人应尽可能沿障碍物边界运动． 对于问题一，依据路径最优原则，确定转弯半径为10个单位，建立了机器人从区域中一点到达另一点的避障最短路径的优化模型．利用MATLAB 求解得到结果如下：A O →:总时间为：96.00826秒，总路程为471.0372个单位；B O →:总时间为179.09982秒，总长度为853.7113单位；C O →:总时间为239.72602秒，总路程为1100.19单位；O C B A O →→→→：总路程：2794.512单位 ，最终总时间为598.5477秒．对于问题二，要使机器人行走时间最短，需在尽可能保证最短路径的基础上适当增加转弯半径．利用几何知识推导出机器人行走时间与转弯半径的关系，时间对半径求导，并令导数为零，得出最短时间所对应的半径5055.11=r ，进而建立最短时间路径的优化模型．利用MATLAB 软件求解得，当机器人从)0,0(O 出发到达A 时，所用最短时间为2130.94秒，总距离为470.8301个单位．关键词：导数；橡皮筋算法；优化模型一、问题的重述图1是一个800⨯800的平面场景图，在原点)0,0(O 点处有一个机器人，它只能在该平面场景范围活动．图中有12个不同形状的区域是机器人不能与之发生碰撞的障碍物，障碍物单位数学描述如下表：表1．12个不同形状区域的特性障碍物的距离至少超过10个单位）．规定机器人的行走路线有直线段和圆弧组成，其中圆弧是机器人的转弯路径．机器人不能折线转弯，转弯路径由与直线路径相切的一段圆弧组成，也可以由两个或多个相切的圆弧路径组成，但每个圆弧的半径最小为10个单位．为了不与障碍物发生碰撞，同时要求机器人行走线路与障碍物间的最近距离为10个单位，否则将发生碰撞，若发生碰撞，则机器人无法完成行走．机器人直线行走的最大速度为50=v 个单位/秒．机器人转弯时，最大转弯速度为21.01001)(ρρ-+==e v v v ，其中ρ是转弯半径．如果超过该速度，机器人将发生侧翻，无法完成行走．请建立机器人从区域中一点到达另一点的避障最短路径和最短时间路径的数学模型．对场景图中4个点)0,0(O ，)300,300(A ，)700,100(B ，)640,700(C ，具体计算：（1）机器人从)0,0(O 出发，A O →、B O →、C O →和O C B A O →→→→的最短路径．（2）机器人从)0,0(O 出发，到达A 的最短时间路径．注：要给出路径中每段直线段或圆弧的起点和终点坐标、圆弧的圆心坐标以及机器人行走的总距离和总时间 ．图1 800⨯800平面场景图二、问题分析对题目条件进行分析：要求目标点与障碍物的距离至少超过10个单位，又知O 点坐标为（0,0），即边界不视为障碍物，但目标点不能超出界限．规定机器人的行走路径由直线段和圆弧组成，其中圆弧是机器人转弯路径，转弯路径只能由一段圆弧组成也可以由两个或多个相切的圆弧路径组成，但每个圆弧的半径最小为10个单位，因为半径趋于0的时候，圆弧长度趋于0，圆弧趋于折线．机器人行走路径与障碍物之间的最近距离为10个单位，否则发生碰撞，即可将障碍物区域向外扩充10个单位，余下部分为目标点可行走范围，对条件中所给最大转弯速度21.01001)(ρρ-+==e v v v 进行分析，当半径∞→ρ时，即可视为直线运动，50==v v 个单位/秒；当半径10→ρ时，最小速度5.220min ==v v 个单位/秒；半径ρ越大，机器人转弯速度越大． 对问题一分析：机器人从)0,0(O 出发，A O →、B O →、C O →和O C B A O →→→→的最短路径问题．首先分析A O →，在没有障碍物的情况下，A O →两点间线段最短，但在两点之间有正方形障碍物5阻碍，必须绕开障碍物5到达A ，要使A O →路径最短，则实际路径越逼近OA 线段越短．根据目标点的位置，可以猜想出机器人的几种避障路径．同理分析B O →、C O →路段．当分析O C B A O →→→→路径时，采用分段处理的方法，将其分为A O →、B A →、C B →、O C →；使各分段路径最短，最后将分段路径综合起来也是最短．对问题二分析：机器人从)0,0(O 出发，到达A 的最短时间路径．在前文条件分析中，半径ρ越大，机器人转弯速度越大，速度v 越大．在问题一最短路径基础上，在转弯路段进行优化处理，适当增大转弯半径ρ，速度增大，与此同时转弯路段圆弧长度必然增加，综合使得到达目的地总时间最短．最后将给出路径中每段直线段或圆弧的起点和终点坐标、圆弧的圆心坐标以及机器人行走的总距离和总时间 ．三、模型假设1．假设机器人在行进过程中为质点；2．假设机器人直线路段以速度50=v 个单位/秒行进；3．假设机器人在各转弯路段匀速行进；4．假设机器人从直线段至圆弧段，速度由直线行进速度瞬间降至转弯速度，速度不存在过度阶段；5．假设平面范围边界不是障碍物，不要求目标点与边界的距离至少超过十个单位，机器人目标点不出界即可．四、符号说明i l 表示机器人每段路径，2,1=i ；r 表示转弯半径；i t 表示机器人所用时间，2,1=i ；i ω表示 第i 段圆弧对应的圆心角；⎩⎨⎧=,0,1其它个切点与目标点相连个障碍物第第j i m ij ； ),(ij ij ωτ表示切点坐标．五、模型的建立与求解问题一模型的建立模型准备：根据对问题的分析及两点之间直线最短的原理，为使机器人能以最短的路径避过障碍达到目标点，应使所走的路线尽可能的接近两目标点的连线，对此，可以猜想出几种机器人行走的路径并对其进行探索．首先对机器人所能行走的区域进行分析，根据题意，需要将区域向外扩展10个单位，区域边界角也应扩展10个单位，即机器人能运动范围是由4/1圆弧和相应的线段围成的，具体结果如下图1所示：200400600800Y图1：机器人行走范围图假设机器人可以看成是一个支点，则机器人可以在边界线上运动而不会发生碰撞．为使得机器人能以最短路径避过障碍物，首先进行局部分析，考虑A O →段路径，由图可知：（1）若无障碍物，A O →最短路径为OA 线段；（2）A O →路段被障碍物5阻隔最短路径探索．探索最短路径原则：实际路径越逼近OA 线段越优．①先不考虑弧长问题，探索大致路径.图3（a ）.路径一 图3（b ）路径二路径一是机器人在保证尽量沿边界线运动的情况下得到的．要从O 点到达A 点，机器人必须绕过边界角，根据两点之间直线最短的原理，可以得到图3（b ）的路径二．通过比较，可以得出：在尽可能沿OA 路径行走的前提下，不需要转弯就能到达的路径尽量选用直线路径，减少圆弧路径阶段，使路径得到优化．②转弯圆弧半径相等时，目标点在不同地点转弯，探索较优路径．2B如图所示，三段弧33B A 、22B A 、11B A 对应圆半径相等且依次远离障碍物,离AB 线段的距离越来越远．以A 为圆心，3AA 为半径画弧，分别交1A 、2A ;同理以B 为圆心，3BB 为半径画弧； 即3AA =2AA =1AA ，3BB =2BB =1BB ；显然11B A →的距离最大，22B A →距离次之，33B A →距离最小；所以由B A →最段路径选择B B A A →→→33．由此可得出结论：在确定转弯圆弧半径的情况下，机器人转弯越靠近障碍物，行走路线越接近两目标点之间的连线，总路程越小．③在距障碍物最近的前提下，考虑圆弧半径的影响，确定最短路径．自定义：边界圆弧中点称为节点．通过②中结论可知：在确定转弯圆弧长度的情况下，机器人转弯越靠近障碍物，行走路线越接近两目标点之间的连线，总路程越小．由机器人所能行走的区域范围及转弯半径至少为10的约束可知，画出的4/1圆弧边界是机器人行走最短路径的边界，若需增大转弯半径，只能在节点处进行变化，否则将超出机器人行走范围．节点是边界圆弧的中点．现判断在节点处，转弯半径对最优路径选择的影响．各图形顶角所对应的外围10个单位区域为边界圆弧，该圆弧为转弯最小圆弧．过最小圆弧节点做与节点相切的半径大于10个单位的圆及相应的路径，如下图3（c ）中的2号路径．图3．（c ）路径三可做如下猜想：圆弧的半径越小，机器人从第一个目标点到达目的地总路程越小．下面对猜想进行证明：A图4：证明猜想示意图如图4所示，以O 为圆心，半径为r 画圆，BD 与圆O 相切，切点为D ，AC 与与圆O 相切，切点为C ；角ωγβα,,,位置如图所示．设A 点坐标为),(11b a ,B 点坐标为),(22b a ,圆心O 点坐标为),(y x ．AC =1l ，CD 弧长=2l ，BD =3l ,由几何知识可得： 2121)()(a x b y a -+-=，2222)()(a x b y b -+-=，212212)()(b b a a c -+-=，在C Rt AO ∆和BOD Rt ∆中，可得：a r=αcos ，b r=γcos ，由余弦定理得： ab c b a 2cos 222-+=β，B A →总路程为=L 1l ＋2l ＋3l ，221r a AC l -==,223r b BD l -==，=L 22r a -+22r b -+r ⋅ω，γβαπω---=2，∴总长度L 与转弯半径r 的关系式为：=L 22r a -+22r b -+r ⋅---)2(γβαπ，为寻求总长度L 与转弯半径r 的具体关系，将L 对半径r 求导，即:)arccos arccos 2(2222b r a r rb r r a r dr dL ---+--+--=βπ )1111(2222b r b a rar -+-+ 化简得：br a r dr dL arccos arccos 2---=βπ， πβ<，当且仅当O B A ,,三点共线时，πβ=，此种情况下不存在两个切点． 角γα,均在直角三角形内，非直角，∴πγα<+． 综上所述：0arccos arccos 2>---=br a r dr dL βπ． 即：总路程L 关于半径r 的函数单调递增，机器人从一个目标点到另一个目的点行走的总路程随着转弯圆弧半径增大而增加．故，猜想：圆弧的半径越小，机器人从第一个目标点到达目的地总路程越小，是正确的．由于机器人转弯半径至少为10个单位，要使行走路径最短，转弯半径10=R .经过上述对机器人避障路线的探究，可得为使机器人行走最短路径，需遵循以下几个原则：1.所走路线应尽可能接近两目标点的连线；2.转弯半径越小越好；3．找不到两圆间的公切线时，机器人应尽可能的沿障碍物边界运动．模型的建立：根据以上原则，可以建立机器人从一个目标点到达另一个目标点的最短路径优化模型．设切点坐标为),(ij ij ωτ，表示第i 个障碍物第j 个切点．通过对路径的探索，可知机器人的路径是由直线和一条或多条圆弧组成的．在此模型中，假设机器人的路径是分阶段的，每一阶段的路径由一条线段和一段圆弧组成，包括了一条线段和多条圆弧的情况．如第１段路径中，线段和圆弧相连，在第２段路径中，线段与第１段路径中的圆弧相连，当此线段长度为０时，机器人从第１段起点到第２段末点的路径就是由一条线段和两段圆弧组成的．线段的长度1l 可由两点间的距离公式解得：2122121)()(y y x x l -+-=．圆弧的角度为ω，半径为r ，则圆弧弧长2l ：ω⋅=R l 2．已知切点时，圆弧角度ω为：R y y x x 2)()(arcsin 2212212-+-⨯=ω．机器人从第一个目标点（11,n m ）到第二个目标点（22,n m ）过程中，⎩⎨⎧= ,0,1其它个切点与目标点相连个障碍物第第j i m ij ， 此时要避过i 个障碍点，设从第一个目标点出发到达另一处时，0=i ，则线段部分长度 :22)2)(2(22)2)(1()1()1(2)1()1(2010221102210121011)()()()()()()()(n m n m l j i j i j i j i j i j i -+-+-+-+-+-+-+-=++++++++ωτττωωττωωωτ,同理，此时对应的圆弧长度：∑=-+-⋅⨯=12122122122)()(arcsin2i i i i i R R l ωωττ.为使机器人行走路径最短，即：21min l l +.综上，可以建立最优规划模型：21min l l +∑∑==-+-⋅=2112221)()(j i k ij k ij ij n m m l ωτ ∑∑==++++-+-+120212)1()1(2)1()1()()(i j j i j i j i j i ττωω 2,1=k∑=-+-⋅=12022122122)()(arcsin2i i i i i R R l ωωττ.10=R问题二的模型建立要使机器人从一个目标点到达另一个目标点所用的时间最短，需考虑行走总路程与速度的影响．对条件中所给最大转弯速度21.01001)(ρρ-+==ev v v 进行分析可知，当半径∞→ρ时，即可视为直线运动，此时50==v v 个单位/秒；当半径10→ρ时， 最小速度5.22min ==v v 个单位/秒，即机器人的速度范围为2.5到5.且半径ρ越大，机器人转弯速度越大．所以为追求最小时间，应在模型一的基础上适当增大转弯半径．同样要保证总路程尽可能的短，机器人转弯时要接近障碍物，即所走路线应尽可能接近两目标点的连线．故可以在最小圆弧基础上增大转弯半径，以下讨论速度与半径之间的关系．如上述图4所示，总路程由线段长度和圆弧长度组成．a r =αcos ，b r =γcos ，abc b a 2cos 222-+=β，221r a AC l -==,223r b BD l -==，=L 22r a -+22r b -+r ⋅ω，γβαπω---=2，=L 22r a -+22r b -+r ⋅---)2(γβαπ，则总时间 21t t t +=，22221v r b r a t -+-=， v r t ⋅=ω2即总时间t 为：2222v r b r a v rt -+-+⋅=ω21.01001)(r ev r v v -+==t 对半径r 求导:)arccos arccos 2((122220b ra r rb r r a r v dr dt ---+--+--⨯=βπ ))2.0()arccos arccos 2(21.010r e b r r r a r r r r -⋅⋅⋅-⋅-⋅-+⋅-βπ)1())1111(21.0102222r e br b a r a r ⋅-+⨯-+-+化简得：)2.01()arccos arccos 2(221.0101.010r r e e br a r dr dt ⋅-⋅-⨯-+⋅---=βπ， 令导数 0=drdt, 由模型一可知：bra r arccos arccos 2---βπ0>,解得当5055.11=r 时，0=drdt．且函数在 )5055.11,10(∈x 区间内是单调递减的，在5055.11>x 时是逐渐增大的，故要使时间最短，满足5055.11=r ．模型的建立：模型二是在模型一的基础上增大转弯半径得到的，是追求最短时间和最短路径的双目标规划问题．建立模型如下：21 t min t +21min l l +..t s ∑=-+-⋅=1222122122)()(arcsin2i i i i i RR l ωωττ∑∑==-+-⋅=2112221)()(j i k ij k ij ij n m m l ωτ∑∑==++++-+-+120212)1()1(2)1()1()()(i j j i j i j i j i ττωω，2,1=k11v l t =， v l t 22=，.5055.11=r问题一、问题二模型的求解：根据建立的模型可利用橡皮筋算法]1[探索最短路径．机器人行走时，如果不知道确定路线时，可以先假设机器人会朝着目的地的方向走，如图3(a)中的A O →；如果中途碰到障碍物，就试图绕过障碍物，再重新朝向目的地的方向行走，如图所示A c b a O →→→→，其中绿色的圆点S 表示出发点，红圆点T 表示目的地．实际上，如果视觉上没有障碍，运动者会选择较近的直切障碍物边沿的行走路线，如图3(b)所示A c b O →→→．这种形状，就像在出发点和目的地之间拉了根橡皮筋，由于障碍物的存在，橡皮筋不能横穿过去，所以沿障碍物边沿拉伸，而正是因为橡皮筋具有的弹性，使得路径趋于最短．根据这种思路，提出了自动漫游路径生成的橡皮筋算法．根据制定的三条原则：1.所走路线应尽可能接近两目标点的连线；2.转弯半径越小越好；3．找不到两圆间的公切线时，机器人应尽可能的沿障碍物边界运动．可以得到机器人从)300,300()0,0(A O →的几条最优路线，如图5所示：200400600200400图5：A O →最短路径示意图从图中可以看出，从)300,300()0,0(A O →有两条路线需要比较计算，利用MATLAB 软件求解得到结果如下（长度单位为单位）：A O →最优路径为：A b a O →→→00．总路程分为2条线段和1段圆弧．其中，各起终点坐标、圆弧圆心坐标及相应的弧长、线段长度分别是： 线段OC ：O （0，0）→C (70.4825，213.0686) 长度224.4237弧CD ： C (70.4825，213.0686) →D （76.4914,219.3643）圆心（80,210）长度9.0041 线段DA ： D （76.4914,219.3643）→A （300,300） 长度237.6094 总时间：96.00826秒 总路程471.0372单位同理可以根据原则得到从O 到B 的几条路线，如图6所示：可编辑200400600800200400600800XY图6：B O →最短路径示意图利用MATLAB 软件求解得到结果如下： 从)700,100()0,0(B O →的最优路径为：B L K J I h f e d c b O →→→→→→→→→→→其中，各起终点坐标、圆弧圆心坐标及相应的弧长、线段长度分别是：线段: Oa )6396.301,1353.50()0,0(a O → , 长度：305.7777 弧ac : ）圆心（300,60, )5474.305()6396.301,1353.50(c a →， 弧长：4.3214 线段cd : )40.5474141.6798,4( )5474.305(d c → 长度：162.1731 弧de ： )435,150, )44.7901147.9621,4()40.5474141.6798,4(圆心（e d → 弧长：7.7751线段ef ： )60.2099222.0379,4()44.7901147.9621,4(f e → 长度： 75.6637 弧fh ： )470,220 (230,470),)60.2099222.0379,4(圆心（h f → 弧长：13.6556 线段hI ： )530,230((230,470)I h → 长度：60 弧IJ ：)530,220 , )3534.538,4967.225()530,230(圆心（J I → 弧长： 9.8883 线段JK ： ,6462915 503314435345384967225). ,.K() .,.J(→ 长度：96.9537 弧KL ： )600,150 ,)96.3458140.6916,5()91.6462144.5033,5(圆心（L K → 弧长：6.1474线段LB ：,)700,100()96.3458140.6916,5(B L → 长度：111.3553 总路程为853.7113 个单位 总时间： 811.9235秒同理可以根据原则得到从O 到C 的几条路线，如图7所示200400600800Y图7：C O →最短路径示意图机器人C O →段路径有4条，利用MATLAB 求解得出结果如下：最优路径为：C k J I H f e d c b a O →→→→→→→→→→→1111111111其中，各起终点坐标、圆弧圆心坐标及相应的弧长、线段长度分别是：线段1Oa ：)0.2262232.1149,5()0,0(1a O → 长度： 237.4868 弧11b a ：）圆心（60,230 , )5.2128238.7797,5()0.2262232.1149,5(11b a → 弧长：8.5850线段11c b ：)34.7872391.2203,3(c )5.2128238.7797,5(11→b 长度：318.4336 弧11c d ： )330,400( , )39.8254398.1397,3()34.7872391.2203,3(c 11圆心d → 弧长：8.8448线段11e d ：371.3965)(564.8828,)39.8254398.1397,3(11e d → 长度：169.7056 弧11f e ： )450,550( 400.4069),(612.7736,f 371.3965)(564.8828,11圆心→e 弧长：57.2031线段11h f ：510.0731)(718.7935,h 400.4069)(612.7736,f 11→ 长度：152.5349 弧11I h ： )520,720( (730,520),I 510.0731)(718.7935,h 11圆心→ 弧长：16.9174 线段11J I ：(730,600)J (730,520)I 11→ 长度：80弧11k J ： )600,720(, 606.3589)(727.7178,k (730,600)J 11圆心→ 弧长6.8916 线段C k 1： C(700,640) 606.3589)(727.7178,k 1→ 长度：43.5890 总路程：1001.7499+98.4401=1100.19单位 总时间：200.34998+39.37604=239.72602秒同理，找出O C B A O →→→→的最优路径，如图8所示：200400600800Y图8：O C B A O →→→→最短路径示意图利用MATLAB 求解得出各起终点坐标、圆弧圆心坐标及相应的弧长、线段长度分别是：弧22d c ：2c (292.7141, 280.3754) →2d (299.3452, 293.5596)圆心（300,300） 长度：16.5989线段22e d ：d2(299.3452, 293.5596) →2e （229.7932，532.02307）长度 248.3995 弧22f e ：2e （229.7932，532.02307）→2f （225.4967，538.3538）圆心：（220,530）长度7.8147线段22i f ：2f （225.4967，538.3538）→2i （140.4000,597.200） 长度103.4617 弧22i h ： 2h （144.5033,591.6462）→2i （140.4000,597.200）圆心（150,600） 长度7.0503线段22j i :2i （140.4000,597.200）→2j (92.000，694.000) 长度108.2257 弧22k j ： 2j (92.000，694.000) →2k （102.3208,709.7270） 圆心（100,700） 长度24.4852线段22l k ：2k （102.3208,709.7270）→2l （270,690） 长度168.8356 弧22m l ：2l （270,690）→2m （272，689.7980）圆心（180,770）， 长度2.0136线段22n m ： 2m （272，689.7980）→2n （368,670.2020） 长度97.9796 弧22o n ：2n （368,670.2020）→2o （370,670）圆心（370，680） 长度2.0136 线段22p o ： 2o （370,670）→2p （430,670） 长度60 弧22q p ： 2p （430,670）→2q （435.5878,671.7068）圆心（430,680）长度5.9291 线段22r q : 2q （435.5878,671.7068）→2r (534.4122,738.2932) 长度119.1638 弧22s r ： 2r (534.4122,738.2932) →2s （540,740）圆心（670,600） 长度5.9291 线段22t s ：2s （540,740）→2t （670,740） 长度130 弧22u t ： 2t （670,740）→2u （679.7725,732.1211）圆心（670,730）长度13.5707 线段22v u ： 2u （679.7725,732.1211）→2v （700.2275,637.8789） 长度96.4365 弧22w v ：2v （700.2275,637.8789）→2w （702.6928,633.1732）圆心（700,640） 长度5.3769最终总路程：2794.512 单位； 最终总时间：598.5477秒 问题二的求解问题二是在建立最短时间优化模型的基础上求解出从O 到A 的最短时间．根据建立的模型，可知当转弯半径5055.11=r 时，时间有最小值．因为 21.01001r ev v ⨯-+=，此时转弯时机器人的速度： 81115.4=v ． 利用问题一的方法解得各起终点的坐标、圆弧圆心坐标如下： 线段Oa ：)210,70(00a O →），（； 弧ab ：)3992.219,0916.78()210,70(b a →， 圆心为（81.5055,210）)300,300()3992.219,0916.78(A b →；总时间2130.94=t 秒， 总距离470.8301单位．模型检验对于问题一的模型检验，由于软件CAD 在处理图形、获取坐标方面较方便快捷，利用CAD 可以自动读取坐标、线段长度、弧长的优点，粗略的估计从A O →、B O →、C O →和O C B A O →→→→的可能较短路线，由CAD 软件可求得得粗略解．将在Autocad 中得到的结果与计算值相比较得表如下：短路线中的最短路径，因此本模型在解决机器人避开障碍物探索最短路径是相对较客观合理的．模型的评价与推广优点：（1）：本模型借鉴“橡皮筋算法”的精华的思想基础，并改良其不足，利用改良后的“橡皮筋算法”使解决机器人机器人避开障碍物探索最短路径的问题变得生动形象，化抽象为具体，使本模型在其它类似问题方面的迁移性较强．（2）：本模型充分体现数形结合思想，在处理机器人行走路线由直线到曲线、由曲线到直线等问题时，巧妙利用解析几何中，圆的切线、两圆公切线处理，同时，采用CAD 软件进行图像上的检验，使本模型在几何关系、数学关系上得出的结果都是客观合理的．缺点：由于行走路线的限制，且路线的连续性以及机器人只能利用圆弧拐弯，因此求出的拐点（直路线线和圆弧切的点）基本上是小数，而且本模型中只精确到0.0001，可能会给具体的机器人实践行走时带来误差．模型的推广：本模型可用于推广解决机器人快速灭火，迷宫路径探索等相似路径的探索问题，也可推广至交警疏通堵车问题中路径规划问题．参考文献[1] 陈勇，王栋，陈戈，一种三维虚拟场景自动漫游的快速路径规划算法，系统仿真学报，第19卷，第11期：2508-2510页，2007.[2] 杨文茂，李全英，空间解析几何，武汉大学出版社，2006.[3] 胡良剑，孙晓君，MATLAB数学实验，高等教育出版社，2006.附录附录1：%两圆公切线，两圆大小相等．求切点%保存为函数wfunction wa1=80+1.5055;b1=210;a2=720;b2=600;%两圆圆心坐标[x,f,h]=fsolve(@li,[a1,b1])endfunction f=li(x)a1=80+1.5055;b1=210;a2=720;b2=600;%zx=(a1+a2)/2;zy=(b1+b2)/2;%两圆相切zx=300;zy=300;%zx=0;zy=0;%直线与圆相切时f(1)=(x(1)-a1)^2+(x(2)-b1)^2-10^2;%在某圆上f(2)=(x(1)-zx)^2+(x(2)-zy)^2+10^2-((zx-a1)^2+(zy-b1)^2);%与两圆圆心连线的中点构成勾股定理end附录2：%求弧长公式要每个点迭代clear;clc;R=11.5055;x1=78.0916;y1=219.3992;%第一点坐标x2=70;y2=210;%第二点坐标f=R*2*asin(sqrt((x2-x1)^2+(y2-y1)^2)/2/R) %弧长附录3：%两圆公切线，两圆大小不等function oformat short[x,f,h]=fsolve(@laz,[580 450])endfunction f=laz(x)f(1)=sqrt((550-x(1))^2+(450-x(2))^2)/(sqrt((720-x(1))^2+(520-x(2))^2))-8;f(2)=7/17*x(1)+3800/17-x(2);end附录4：%算线段长度，要迭代clear;clc;R=10;x1=0;y1=0;%第一点坐标x2=50.1353;y2=301.6396;%第二点坐标f=sqrt((x2-x1)^2+(y2-y1)^2) %线段长度.。
