论文部分内容阅读
近几十年来,路径规划问题在很多领域一直备受研究者的关注,例如移动机器人,无线传感器网络,视频游戏,无人驾驶车辆等等。在移动机器人领域,路径规划是在有界空间中找到从起点到目标点的一条或多条可行路径。在很多路径规划问题中,仅仅考虑避障是远远不够的。往往需要考虑多个优化指标,比如机器人行进路线的能量消耗、路径安全系数等等。这些指标互相矛盾,彼此制约。一个指标性能提升的同时往往会导致其他至少一个指标退化,即多个指标很难同时达到最优。所以,多目标路径规划问题一直是一个普遍关注的话题。本文旨在从确定性算法和基于种群的进化算法两个角度展开研究,本文的创新性工作概述如下:在第二章将确定性、面向集合的胞映射算法首次应用于路径规划研究领域,求解多目标最优化问题。设计了路径长度和安全度两个优化指标。胞映射算法可以找到离散网格空间中所有胞到目标胞的非支配代价集合,即求解了单源多目标优化问题。为了进一步地提高胞映射在路径规划问题中求解的计算效率和计算精度,在第三章提出了基于细分技术的混合胞映射算法。类似于决策空间内可行域的概念,提出了路径空间覆盖域的概念,并基于细分技术对覆盖域进行细分,形成精度更高的网格空间,再运用胞映射算法来求解。最后,对比了混合胞映射和胞映射的数值计算结果。数值计算结果显示,混合胞映射生成的非支配Pareto前沿更加均匀分布且更接近于真实的Pareto前沿。并且由于网格更加精细,尽管没有考虑路径平滑度指标,但是可以很清晰地看到路径更加平滑。在第四章针对路径规划问题提出了一种新的进化算法。不同于非支配排序遗传算法设计的精英策略来保留优良的个体(解)以及维持种群内个体的多样性,而是提出了将目标函数空间网格化,用格子内解的数量的多少来表示格子的适应度函数值。格子内解的数量越少,格子的适应度函数值越大,该格子内解被选取的几率越高。另外,设计了一种新颖的进化算法的框架以及多个实用的进化算子。这些算子可以提高解的品质。并且用Dijkstra算法生成一部分局部最优解,并将它们放入初始种群来进一步提高算法进化的效率。最后,将提出的算法和粒子群算法进行了对比,并且用品质度量方法(超体积指标和集合覆盖度量)评估了对比结果。数值结果显示,提出的算法得到的非支配解有良好的特性。在第五章提出了改进的非支配排序遗传算法来解决路径规划问题。设计了多个进化算子,来进一步提高解的品质。另外,对算法中涉及的参数进行了深入的研究。研究结果显示,在复杂的环境中,大的种群规模、代数和高的算子概率可以显著地提高求解的效率。最后,将改进的遗传算法和上一章的进化算法进行了对比,并且用品质度量方法评估了对比结果。数值结果显示,两种算法都可以得到具有良好特性的非支配解集。另外,非支配解集中的拐点对应的路径更短,更平滑以及更安全。可以在之后的决策过程中被决策者采纳。本文提出了求解静态环境中移动机器人多目标路径规划问题的两类算法。其中包括确定性的胞映射算法和基于种群演化策略的进化算法。胞映射算法从全局角度找到离散工作空间中任一个胞到目标胞的非支配代价集合(数据库),而后基于该数据库,可以找到起始胞到目标胞的最优路径。接着提出了混合胞映射算法来进一步提高算法的效率和精度。进化算法是从种群演化的角度来求解问题。一系列进化算子作用于种群(路径集合)后生成新的种群。经过多次迭代,种群发现的非支配解集不断地朝真实的Pareto前沿逼近。在本文中介绍了两种进化算法的设计过程。