基于快速扩展随机树的仓库机器人路径规划算法研究开题报告

1. 研究目的与意义（文献综述）

近年来，随着电子商务的迅猛发展，使得作为其支撑核心的物流面临着巨大的挑战。作为电子商务对物流的最大需求点之一,仓储物流正发生着巨大的变革^[1]。传统的仓储物流由于效率低下已经难以满足现代电子商务业的需求。从上世纪70年代起，多机器人系统开始成为人工智能和机器人领域的一个重要研究方向^[2]。但是，多机器人系统决不是单机器人的简单叠加，通过解决机器人间的协作问题后，多机器人系统的合作结果往往很大程度上要优于多台机器人独立工作结果的直接相加^[3]。

作为机器人研究领域的一个重要分支,路径规划技术在航空航天、人类生活、物流行业、汽车工业等领域都得到了广泛应用。通过对机器人导航和路径规划的研究可以发现，路径规划算法的发展经历了传统算法诸如a*算法、d*算法、人工势场法、模糊规则法、快速扩展随机树(rapidly-exploring random tree, rrt) 算法等^[4]-[13]。除此之外，还出现了一些智能仿生学算法如蚁群算法、粒子群算法、遗传算法和神经网络等。

近年来, 由s．m．lavalle于1998年提出的rrt算法得到广泛应用^[14]。rrt算法建立的思想来自于最优控制理论，非完整规划，随机路径规划。rrt算法更适合解决高维空间和复杂约束下的路径规划问题，在移动机器人路径规划算法中应用较为广泛，它避免了对环境信息的建模，具有较强的路径搜索能力。但是，由于该算法自身的随机性使其收敛速度较为缓慢,在算法的性能上依然有很多的不足需要改进和完善，因此得到了国内外学者的关注和研究。例如，elbanhawim30等人利用b样条曲线降低了搜索维度，并通过双向rrt算法将随机搜索方法的主导探索性质与向量值参数化转向相结合,在不受传统动力学规划器的数值积分和控制空间离散化的阻碍的情况下，设计出了满足车辆局限性以及障碍物约束的运动规划器。karaman s等人基于采样的方法提出将环境中的障碍物分为有价值和无价值的障碍，当障碍物位于起始点和日标点之间时，采用边界信息在障碍物周围进行采样，有效降低了无效的采样点数量,使扩展树始终朝着目标点的方向扩展，加快了算法的收敛速度。noreen t等人^[15]提出了一种基于rrt*的离线规划算法rrt*可调边界(rrt*-ab)。该方法快速地将目标区域作为目标，通过连通区域、目标偏置的有界采样和路径优化三种新策略，提高了计算效率，在减少时间和存储需求的情况下快速收敛到更短路径。

2. 研究的基本内容与方案

本次毕业设计的主要研究内容是:对智能仓库中多移动机器人的拣货路径规划算法展开研究，实现基于快速扩展随机树的路径规划算法，使得智能仓库中多机器人协同配合，共同完成规定指定任务。

在这个设计过程中我们的目标是：克服传统的路径规划算法都需要在一个确定的空间内对障碍物进行建模，计算复杂度与机器人自由度呈指数关系，不适合解决多自由度机器人在复杂环境中的规划的问题。利用基于rrt路径规划算法，对状态空间中的采样点进行碰撞检测，避免对空间的建模，能够有效地解决高维空间和复杂约束的路径规划问题。

基于快速扩展随机树的机器人路径规划算法是一种在多维空间中有效率的规划方法。它通过一个初始点作为根节点，通过随机采样，增加叶子节点的方式，生成一个随机扩展树，当随机树中的叶子节点包含了目标点或进入了目标区域,便可以在随机树中找到--条由树节点组成的从初始点到目标点的路径。通常分为节点采样，节点扩展，碰撞检测，终点策略，终止条件判断以及剪枝处理这几个过程。

3. 研究计划与安排

1）第1周—第3周 搜集资料，撰写开题报告；

2）第4周—第5周 论文开题；

3）第6周—第12周 撰写论文初稿；

4. 参考文献（12篇以上）

1. 从行健.浅析自动化技术在智能物流系统中的应用——以京东无人仓库为例[J].中国战略新兴产业，2018(4):53-55.

2. 陈建平，任斌，张会章.人工智能在智能机器人领域中的研究与应用[J]．东莞理工学院学报,2008,15(3):33-37.

3. 陈秋莲,蒋环宇,郑以君.机器人路径规划的快速扩展随机树算法综述[J].计算机工程与应用,2019,55(16):10-17.
4. 张广林，胡小梅，柴剑飞，等.路径规划算法及其应用综述[J].现代机械，2011(5):85-90.
5. 王小伟.室内自主导航轮式机器人路径规划策略研究[D].合肥：合肥工业大学，2018.
6. 朱轶.基于改进RRT～*算法的路径规划[J].武汉理工大学学报，2017(2):72-76．
7. Cui R, Li Y ,Yan W . Mutual Information-Based Multi-AUV Path Planning for Scalar Field Sampling Using Multidimensional RRT*[J].IEEE Transactions on Systems, Man, and Cybernetics: Systems. 2017,46(7):993-1004.
8. 杨傥月,汪秀忠,陈自豪,梁洛萌.基于改进RRT算法的机器人自主环境探测[J].信息技术,2019,43(12):20-28.
9. 杨也,倪建军,陈一楠,陈颜.改进RRT*的室内机器人路径规划算法[J].计算机测量与控制,2020,28(01):241-245.
10. Adiyatov O ,Varol H A .A novel RRT*-based algorithm for motion planning in Dynamic environments[C].IEEE International Conference on Mechatronics Automation. IEEE, 2017.
11. Hidalgo-Paniagua A , Bandera J P , Ruiz-De-Quintanilla M，et al. Quad-RRT: A real-time GPU-based global path planner in large-scale real environments[J]. Expert Systems with Applications, 2018,99:141-154.
12. Siciliano B, Oussama K. Springer Handbook of Robotics[M].2007.
13. SertacK,EmilioF.Incrementalsampling-basedalgorithmsforoptimalmotionplanning[R].Cambridge, MA:LaboratoryforInformationandDecisionSystems,MassachusettsInstituteof Technology,2010
14. 冯来春.基于引导域的参数化RRT无人驾驶车辆运动规划算法研究[D].合肥：中国科学技术大学,2017.
15. 贾菁辉.移动机器人的路径规划与安全导航[D].硕士学位论文.大连:大连理工大学,2009.
16. 王赟.基于RRT轮式机器人路径规划方法研究[D].天津工业大学,2019.
17. 刘成菊，韩俊强，安康.基于改进 RRT算法的 RoboCup机器人动态路径规划[J].机器人，2017,39(1):8-15.
18. 刘新宇,谭力铭,杨春曦,翟持.未知环境下的蚁群-聚类自适应动态路径规划[J].计算机科学与探索,2019(05)