Path Planning in Complex 3D Environments Using a Probabilistic Roadmap Method
https://link.springer.com/article/10.1007/s11633-013-0750-9

对于无人机而言,路径规划将在 3D 环境中进行,这是一个很大的挑战,尤其是在复杂环境中。常用于高维配置空间的方法是基于采样的方法,包括 PRM[ 15 , 16 ] 及其变体。PRM 有两个阶段:学习阶段和查询阶段[ 15 ]。在学习阶段,为给定场景构建称为路线图的数据结构。路线图是一个无向图R = ( N, E )。N _是一组节点,它们是从无碰撞配置空间中随机采样的点。在图中选择有希望的节点对,并使用本地规划器尝试将这些位置与边缘连接起来。如果它们可以连接,则将边缘添加到E。一个好的图R应该很好地覆盖空闲空间。在查询阶段,路径通常通过路径查询找到,例如 Dijkstra 或 A*。

基本 PRM 的瓶颈在于它难以找到穿过狭窄通道的路径。这是由于自由空间中的随机采样节点导致在狭窄通道中放置的节点太少。一种解决方案是在障碍物边界附近添加配置[ 17、18 ]。尽管这种方法增加了在狭窄通道中采样节点的概率,但狭窄通道之外的许多节点无助于改善路线图的连通性。Hsu 等人[ 19 , 20 ] 提出了一种混合策略:在狭窄的通道中应用桥接测试以增加采样密度,并在开放的自由空间中使用均匀采样策略。在 [ 21],作者通过使用惰性显着边缘算法将新样本放置在尚未导航的区域中来改进惰性概率路径规划。在这些方法中,环境的障碍由几何模型表示。

On the Relationship between Classical Grid Search and Probabilistic Roadmaps
https://journals.sagepub.com/doi/abs/10.1177/0278364904045481

2.4. 针对单一查询的懒惰PRM 最近的PRM变量被称为懒惰PRM,它是针对有效回答单一规划查询的问题而提出的,而不是在考虑规划查询之前建立一个广泛的路线图(Bohlin和Kavraki 2000)。由此产生的规划器与原来的PRM相比有时非常高效。这代表了从原来的PRM(Kavraki等人,1996)的多重查询理念到早期的一些规划器(Faverjon和Tournassoud,1987;Barraquand和Latombe,1990;Mazer等人,1992)中使用的单一查询理念的转变。lazy PRM的关键思想是在不使用碰撞检测器的情况下初步建立路线图。与图1的算法不同的是,第6行的条件被放弃,而第7行每次都被执行。这使得PRM能够快速构建;然而,在查询阶段,搜索的负担更重。一旦给出初始目标查询,规划器就会在路线图上进行A*搜索,以找到解决方案。如果有任何解决方案的边发生了碰撞,它们就会从路线图中被删除,然后重复A∗搜索。最终,所有的边可能都要进行碰撞检查,但通常在这之前问题已经解决了。另外,最好只在初始图上运行一次搜索,同时在搜索过程中验证边(而不是等待解决方案,然后验证它)(Branicky等人,2001)。如果没有找到解决方案,那么可能需要在路线图上添加更多的节点。懒惰PRM的优点是只在需要时进行碰撞检查。因此,所有的边不必像原始PRM那样进行碰撞检查。在CGS中,这一理念意味着位图不是预先计算的;碰撞检查只在搜索过程中根据需要进行。

2022-08-05 跑通现有模型,熟悉各代码模块作用

学习计划:

2022-08-25-2022-08-28

问题:
  1. 栅格化地图模型?PRM概率路径图好像不需要栅格化
  2. 小车在同一时刻只能 前进后退,或者原地旋转?(Entwicklung_eines_kollaborativen_Systems 2.4.3)
计划:
  1. 排除其他干扰,默认摄像头图像处理准确,障碍物识别准确,小车位置定位准确,小车匀速运动的情况下。进行一般情况下的离线无碰撞PRM路径规划:多个小车,其各自的起点和终点都不相同。
  2. 优化PRM随机点分布
  3. 如果发生碰撞,该怎么处理。
  4. 定位:视觉定位,惯性导航。

学习计划:

2022-08-05 至 2022-08-12
跑通现有模型,熟悉各代码模块作用

总结:

1.simulink内建模
2.仓库顶部摄像头
3.机器人与摄像头通信

问题:

1.仓库地图
2.是否有预定路线
3.地图展现形式2D、3D?
4.摄像头只用于碰撞预警?不用于路径规划?

计划:

1.2022-08-10 process on 列出任务大纲

研究生毕业论文

研究生毕业论文

开题报告

题目

Development of collision-free navigation using probabilistic road maps in environments with multiple differential-drive robots

在具有多个差分驱动机器人的环境中使用概率路线图开发无碰撞导航

关键词:多个机器人;概率路线图;无碰撞导航


背景

The future aim is an autonomous warehouse with multiple surveillance and multiple robots. This work shall deal with a simulator which should simulate one camera and multiple robots.

未来的目标是拥有多个监控和多个机器人的自主仓库。 这项工作将处理一个模拟器,该模拟器应该模拟一个摄像头和多个机器人。

The aim of this work is to extent the former works to a multiple robot environment. First the simulator have to be improved and extent to multiple robots. Especially the robot and camera model need to be improved. Next a path planing for one robots using probabilistic road maps (PRM) should be developed. An important task is the strategy of random point generation. This should be extended to a collision-free path planning for multiple
robots, including the definition of a safety distance around each robot.

这项工作的目的是将前者的工作扩展到多机器人环境。 首先必须改进模拟器并扩展到多个机器人。 尤其是机器人和相机模型需要改进。 接下来,应开发使用概率路线图 (PRM) 的机器人路径规划。 一个重要的任务是随机点生成策略。 这应该扩展到多个无碰撞路径规划
机器人,包括定义每个机器人周围的安全距离。

A number of former works, functions and base simulator will be provided (including collision detection, speed controller etc.). Everything should be implemented in MATLAB/SIMULINK with a modular software design.

将提供许多以前的作品、功能和基础模拟器(包括碰撞检测、速度控制器等)。 一切都应该通过模块化软件设计在 MATLAB/SIMULINK 中实现。


任务

1.Incorporation into the existing robot simulator, MATLAB/SIMULINK

与现有机器人模拟器 MATLAB/SIMULINK 相结合

2.Incorporation into (quasi) random data, Path planing, grid map

并入(准)随机数据、路径规划、网格图

3.Improvement and extension of the simulator

仿真器的改进和扩展

4.Development of a PRM-path planning for one robot with differential drive

为一台具有差动驱动的机器人开发 PRM 路径规划

5.Development of a PRM-path planning for multiple robots with differential drive

多机器人差动驱动的 PRM 路径规划开发

6.Implementation, Validation and evaluation in MATLAB/SIMULINK

在 MATLAB/SIMULINK 中实现、验证和评估

7.Design of a GUI using SIMULINK Dashboard and scopes

使用 SIMULINK Dashboard 和示波器设计 GUI

8.Documentation of the working results, which meets the requirements of the Master Thesis

符合硕士论文要求的工作成果文件