Algorithm for high level planning in artificial intelligence

Question

I am currently working on an artificial intelligence project in which agents need 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 positions. 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" 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 the 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

The planning in Artificial Intelligence is about the decision making tasks performed by robots or computer programs to achieve a specific goal.

The execution of planning is about preferring a sequence of actions with a high likelihood to complete the specific task.

What you call a cut position for your grid word is named a cut vertex or articulation point in general graphs.

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

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.

For more information regarding the same, refer to the following link: https://en.wikipedia.org/wiki/Biconnected_component