论文部分内容阅读
移动机器人的广泛应用使得路径规划成为研究热点。时序任务约束的路径规划则是机器人研究中的关键技术之一。线性时序逻辑(LTL)理论为描述机器人的时序任务提供了理论基础,LTL公式规范地描述了复杂的时序任务。目前时序任务约束的路径规划问题有一定的解决方法,但是现有方法的复杂度偏高,在实际应用上具有一定的局限性。多机器人合作完成人们所指定的任务也是机器人研究方向之一。所以,对满足复杂时序任务约束的路径规划方法的优化,以及对多机器人的路径规划研究具有很重要的研究意义。本论文对上述问题做了以下几方面的研究:(1)研究了单机器人静态环境下时序任务约束路径规划方法。现有算法对解决时序任务的路径规划问题具有很好的效果,但是随着任务点的增加,算法响应速度变得非常慢,因此针对现有算法时间复杂度偏高这一问题,提出三种约束准则,对可行型网络拓扑图进行优化,缩减需要搜索的状态点,提高求解过程的速度,并针对底层路径搜索算法的不足,提出利用小根堆的方法优化底层路径搜索算法,提高算法的响应速度。(2)研究了动态环境下基于马尔科夫决策过程(MDP)的单机器人时序任务约束路径规划方法。针对现有算法的不足,提出利用非确定型自动机代替确定型自动机,解决了确定性自动机无法解析一些LTL公式的问题,并把动态环境模型建模成有限加权切换系统,构建可行型网络拓扑图,利用提出的三种约束准则对可行型网络拓扑图进行状态缩减,再根据剩余的状态点构建马尔可夫决策过程,使用具有动态规划性质的值迭代算法代替传统的策略迭代算法,降低马尔可夫决策过程的求解难度,提高算法的响应速度。(3)研究了基于博弈论和LTL的多机器人路径规划方法。针对多机器人的路径规划研究的不足,提出利用经济学中的博弈论来解决满足复杂时序任务的多机器人路径规划问题,将多机器人视为局中人,并将机器人需要完成的任务分解为子任务,利用双画线法求解纳什均衡,每个任务的价值(距离)利用LTL结合路径搜索算法进行求解。让机器人自我判断利益得失(行驶距离),并决定每个机器人需要完成的任务,在合作完成任务的同时,保证取得的价值最高(行驶距离最短)。本文对上述所提出的运动规划方法进行了仿真和实验,结果表明提出的方法处理单机器人和多机器人的路径规划问题具有不错的效果,不仅能够完成复杂时序任务的路径规划问题,还能解决静态环境和动态环境下机器人的路径规划问题,促进机器人在实际环境中的应用。