Algorithm for high level planning in artificial intelligence

Question

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?

Answer 1

What you call a cut position for your grid word is called a cut vertex or articulation point in general graphs. From Wikipedia:

Specifically, a cut vertex is any vertex whose removal increases the number of connected components.

And a bit further down in the same article:

The classic sequential algorithm for computing biconnected components in a connected undirected graph due to John Hopcroft and Robert Tarjan (1973) [1] runs in linear time, and is based on depth-first search. This algorithm is also outlined as Problem 22-2 of Introduction to Algorithms (both 2nd and 3rd editions).

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.

Answer 2

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.