理解Python中基于冲突的搜索MAPF（cbsmapf）包

Question

我正在尝试使用pypicbs mapf package，这是一种基于冲突的多代理路径查找算法。对于示例文件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]]）时，它运行良好，并为我提供了一个计划

My question:

1. 统计障碍小的问题是什么？我无法理解这个错误消息

2. 网格参数实际上反映了什么。每个单元格或整个表格的大小

Answer 1

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

2. 关于网格大小参数的第二个问题。 据我从代码中了解，grid size参数定义了代理可以执行的空间步长的大小，以及障碍物的大小。请注意，代理的大小可能更大（因此，即使它们位于不同的位置，它们也可能发生碰撞）。 e、 如果您选择grid_size = 2，那么您的状态空间将是[[1,1],[1,3],[3,1],...]