多车轨道路径规划算法设计

2021年9月10日 5点热度 0条评论

场景:多车,走最顶层轨道方格,立方仓,多车共同取货。

 

单车路径规划算法选择 

 

 

常用的最短路径规划算法是Dijkstra、A*、D*算法。

Dijkstra算法效率低,D*是对A*的优化版本,减少计算量,区别在于D*以终点为搜索开始点,适合环境变化的场景。优化在于,障碍物变更,可以利用之前的部分计算结果,离终点越远,需要重新计算的计算量越小。由于项目场景最高是100*100的方格,A*已经足够,而且A*的路径更为优化,所以最终选择使用A*算法。

 

多车运动实现方法

多车运动需要考虑的问题是如何不卡死,问题类似于死锁,容易想到的算法是银行家算法、优先级;每量车将要走下一步之前预判是否完成任务,如果不能,停止分配新空间。使用这个方法可以避免绝大多数情况的多车互卡的问题。只是有两个问题:1.少数情况卡死;2.效率低,远处的阻塞也会带来小车等待

问题1是因为多车运动场景和死锁的场景不同,无论如何小车都会占用一定的空间,所以如果互邻的车想走向对方位置,会发生互卡,为了避免卡死,选择卡死时间过长会产生随机运动的策略避免问题。

 

多车运动路径规划最优解

多车运动涉及到多辆小车的互相影响,阻塞等情况。如何寻找最优解。

理论上最优解只有两种可能,第一种是公式,直接算出,第二种是穷举法。

多车运动,是复杂场景,没有公式直接算出。是需要根据当时情况随时会变化。而每辆车,每一秒运动轨迹是(上、下、左、右、不动、取货/放置)六种可能的状态。假设完成一个任务可能需要10秒,假如总共5辆车,以一秒为时间单位,需要穷举的可能性是6的5次方的10次方,也就是8*10的38次方,远远超过计算机运算能力,故最优解无法实现。

当前人类面对最优解不存在,又不想陷入局部最优,所选择的方法原理都一致:使用随机数。例如:蚁群算法、退火算法、粒子算法、遗传算法还有AlphaGo使用的蒙特卡洛随机树,本质都是加入一定的随机数。所以为了避免多车运动陷入局部最优卡死,必须引入随机数。

 

引入随机数带来效率问题

引入随机数会导致小车很容易发生随机运动,重复来回移动,影响效率。

为了增加效率又不能陷入卡死困境,所以引入程序逻辑,尽量避免随机运动:1.通过随机数加权(类似蒙特利尔随机树),同一任务走过的路,随机比重更低,有其他车路径的路,随机比重更低;2.通过程序逻辑设计,优先采取预设定会车策略,例如两车相向行驶,互相阻塞前进道路,先辆车左旋尝试避让,失败了右旋避让……预设策略都失败了,再使用随机防卡死设计。

 

交通阻塞问题-时间片

多车同时走,由于算法一致,容易发生都走一条路问题,为了避免交通拥堵,对每个方格做时间片设计,在a*算法时,对不同方向做一定的加权,拥堵路段权重更低,同时对走直线进行直线加速,走直线权重更高。