一种增加时间维的搜索算法来处理动态障碍物。
space-time-astar的Python项目详细描述
时空A*
一种处理动态障碍物的时空A*（STA*）搜索算法。在
安装
包名为space-time-astar，列在PyPI上。您可以使用pip安装：
pip3 install space-time-astar
{{a2}你可能对这个包{a2}感兴趣，在这个包^-a2}上使用多个代理。在
使用
导入计划器
^{pr2}$构造函数参数
Planner(grid_size:int,robot_radius:int,static_obstacles:List[Tuple[int,int]])
- grid_size：int-每个网格都是边长为grid_size的正方形。在
- robot_radius：int-代理被假定为半径为robot\uradius。在
- static_障碍物：List[Tuple[int，int]]—指定地图中静态障碍物的坐标列表。在
重要的是grid\'u size不要太小，static_障碍不包含太多坐标，否则性能将严重恶化。你可能会问什么是“太多”？这取决于你的要求。在
查找路径
使用Planner的plan()方法：
plan(start: Tuple[int, int],
goal: Tuple[int, int],
dynamic_obstacles: Dict[int, Set[Tuple[int, int]]],
semi_dynamic_obstacles:Dict[int, Set[Tuple[int, int]]] = dict(),
max_iter:int = 500,
debug:bool = False) -> np.ndarray:
参数：
- start：Tuple[int，int]-起始坐标。在
- goal：元组[int，int]-目标坐标。在
- dynamic_障碍物：Dict[int，Set[Tuple[int，int]]]-动态障碍物实际上是时空中的其他代理保留，详细信息如下。在
- 半动态障碍物：Dict[int，Set[Tuple[int，int]]]，optional——这个参数的存在是因为我们必须考虑到已经到达目的地的代理，它们本质上是特定时间的静态障碍。在
- max}iter：int，可选-搜索的最大迭代次数。默认为
500。在 - debug：bool，可选-打印一些调试消息。默认为
False。在
dynamic_barriends的键是表示时间的整数，值是坐标集。它告诉计划者我们在每个时间步需要避免什么样的坐标。目前，假设动态障碍物是其他智能体（具有相同的robot_半径），并且与静态障碍物的处理方式不同。在
返回：
一个numpy.ndaarray，形状(L, 2)，其中L是路径的长度。在
理论背景
Here是大卫·西尔弗（davidsilver）写的一篇关于时空a*（STA*）的好文件。在
简言之，STA*是普通的a*加上时间维度。参见下图。在
在
在左边的块中，第一个代理规划它的路径并保留它的路径穿越时间（与第二个代理无关）。在
在右边的块上，第二个代理计划其路径，同时避免第一个代理保留的路径（即dynamic_bulleries参数）。在
space-time-astar包
中的实现决策
- 在
曼哈顿距离（Manhattan distance）是一种可接受的、一致的启发式算法，在这个实现中被使用。您可以通过更改
在planner.py中的h()函数来更改它。在 - 在
代理可以比网格大。在
在 - 在
假设动态障碍物是相同大小的其他因素。这可以在
在plan()中的safe_dynamic()内部函数中更改。在
贡献
欢迎拉取请求。对于重大变化，请先打开一个问题，讨论您希望更改的内容。在
许可证
- 项目
标签：
欢迎加入QQ群-->： 979659372
