I am currently working on an artificial intelligence project in which an agents needs to push and pull boxes from their original position to a certain goal position. The project will then be expanded to include multiple agents, so we have a supervisor that takes care of creating “high-level” goals, while the agents take care of the actual implementations.

In practice, for the moment, the supervisor should decide the order in which the boxes should be put on goal position. In fact, it could happen that putting a box in its goal position could block the path to another goal.

Our first approach to solve this problem is trying to consider “cut-positions”. A certain position is a cut position if it divides the walkable space into two subsets, in which one of those we have the agent, and in the other we have one or more goals. For example, consider the following level in which “x” is the agent, “A” and “B” are boxes and “a” and “b” are the respective goal positions:

```
+++++++++++++++++++++++++++++++++++++++++
x a b+
+++++ +++++++++++++++++++++++++++++++++
+AB +
+++++
```

In this case the position of goal “a” is a cut position, because if a box is put there, then the agent will not be able to reach goal “b”.

Can you suggest a fast algorithm to compute the cut positions, and that maybe returns the number of goals that each cut position is blocking?

2

## Answers

You could put the area into an undirected graph, where each node is a position of the map and two nodes are connected if the positions are adjacent to each other. Then you can mark those ‘cut positions’ on the graph and see all the paths that would be blocked by a box on a cut position.

What you call a cut position for your grid word is called a

cut vertexorarticulation pointin general graphs. From Wikipedia:And a bit further down in the same article:

Having determined the biconnected components, it should be quite easy to determine the articulation points: All nodes which are contained in more than one bi-connected component are articulation points.