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

Question

我正在尝试使用 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]]

）时，它工作正常并给了我一个计划。

我的问题：

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

2. 还有grid参数实际反映了什么。每个单元格或整个表格的大小？

Answer 1

1. 静态障碍物很小的问题是，如果你的状态空间非常密集且有障碍物，计算可能会很困难。 MAPF 问题是 NP-hard 问题，CBS 解决方案可能需要详尽无遗。 （直觉上，如果障碍物数量少，CBS Constraints Tree 中有更多的潜在叶子是最优的。）
   关于您看到的错误： 由于某些原因，在 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 参数的第二个问题。 据我对代码的理解，网格大小参数定义了代理可以进行的空间步长的大小，以及障碍物的大小。请注意，代理的大小可以更大（因此即使它们位于不同位置，它们也可能会发生碰撞）。 例如如果您选择

   grid_size = 2

   ，那么您的状态空间将为

   [[1,1],[1,3],[3,1],...]

   .

Answer 2

如果你还有问题。与其了解所有细节，不如寻找那些 .yaml 文件： 这是一个：

目标：

• !!python/元组 [800, 100]
• !!python/元组 [800, 200]
• !!python/元组 [800, 300]
• !!python/元组 [800, 400]

GRID_SIZE：50 RECT_OBSTACLES： 0:

• [0, 0]
• [1000, 800] 1:
• [480, 450]
• [490, 460] 机器人半径：40 开始：
• !!python/元组 [50, 50]
• !!python/元组 [50, 150]
• !!python/元组 [50, 250]
• !!python/元组 [50, 550]