python - 了解 Python 中基于冲突的搜索 MAPF (cbs-mapf) 包

问题描述

我正在尝试使用 pypi cbs mapf 包 ，它是一种基于冲突的多代理路径查找算法。对于示例文件scenario1.yaml，它运行得很好。

包安装：

pip install cbs-mapf

但是当我尝试编写自己的代理时，给了我错误。

我的驱动程序代码：

from cbs_mapf.planner import Planner
planner=Planner(grid_size=1, robot_radius= 2, static_obstacles = [[0, 0], [19, 10]] )

print(planner.plan(starts=[[33, 16]],
    goals=[(54, 56)],
    debug=True))

给我一个错误代码：

Traceback (most recent call last):
  File "/home/sayan/Documents/mapf cbs/main.py", line 4, in <module>
    print(planner.plan(starts=[[33, 16]],
  File "/home/sayan/.local/lib/python3.8/site-packages/cbs_mapf/planner.py", line 54, in plan
    solution = dict((agent, self.calculate_path(agent, constraints, None)) for agent in self.agents)
  File "/home/sayan/.local/lib/python3.8/site-packages/cbs_mapf/planner.py", line 54, in <genexpr>
    solution = dict((agent, self.calculate_path(agent, constraints, None)) for agent in self.agents)
  File "/home/sayan/.local/lib/python3.8/site-packages/cbs_mapf/planner.py", line 192, in calculate_path
    return self.st_planner.plan(agent.start, 
  File "/home/sayan/.local/lib/python3.8/site-packages/stastar/planner.py", line 85, in plan
    start = self.grid.snap_to_grid(np.array(start))
  File "/home/sayan/.local/lib/python3.8/site-packages/stastar/grid.py", line 49, in snap_to_grid
    return self.grid[i][j]
IndexError: index 15 is out of bounds for axis 0 with size 10

但是当我改成static_obstacles= [[0, 0], [19, 10]]更大的比如时static_obstacles= [[0, 0], [191, 107]]，它工作正常并给了我一个计划。

我的问题：

统计障碍很小有什么问题？我无法理解错误消息。
网格参数实际上反映了什么。每个单元格或整个表格的大小？

标签： pythonpath-findingpypimazemulti-agent

解决方案

静态障碍物很小的问题在于，如果状态空间中障碍物非常密集，则计算可能会很困难。MAPF 问题是 NP-hard 问题，CBS 解决方案可能需要详尽无遗。（直观地说，如果有少量障碍物，CBS 约束树中有更多潜在的叶子是最优的。）
关于您看到的错误：由于某种原因，在 mapf-cbs 中定义了整个网格的大小通过障碍。这意味着如果您定义static_obstacles = [[0, 0], [19, 10]]然后状态空间是大小为 19X10 的矩形，然后您的开始和结束状态超出范围。请注意，当您选择static_obstacles= [[0, 0], [191, 107]]确实，您的起始状态和监狱状态都在这个三角形内。我的猜测是，作者希望您通过明确定义障碍物（作为框架或两个角）来明确定义状态空间的边界。参见示例场景 2，其中网格内没有障碍物，但作者添加了“矩形障碍物”作为状态空间的边界。我不清楚作者为什么选择这种设计，但至少它回答了你的问题。只是为了得到一个更完整的答案，为了在代码中看到它，检查calculate_boundaries他们定义的函数，例如min_ = np.min(static_obstacles, axis=0)，然后使用它作为状态空间的边界。
关于 grid_size 参数的第二个问题。据我了解，网格大小参数定义了代理可以进行的空间步长的大小以及障碍物的大小。请注意，代理的大小可以更大（因此即使它们位于不同的位置，它们也可能发生碰撞）。例如，如果您选择grid_size = 2，那么您的状态空间将是[[1,1],[1,3],[3,1],...].

python - 了解 Python 中基于冲突的搜索 MAPF (cbs-mapf) 包

问题描述

解决方案

推荐阅读