High-Level Planning Algorithm in Artificial Intelligence

Question

I am currently working on a project on artificial intelligence in which agents must click and pull boxes from their original position to a specific position of the target. Then the project will be expanded to include several agents, so we have a supervisor who takes care of creating “high-level” goals, while the agents take care of real implementations.

In practice, at the moment, the supervisor must decide in which field the target fields should be placed. In fact, it may happen that putting the box in the target position can block the path to another target.

Our first approach to solving this problem is an attempt to “cut positions”. A certain position is the position of the section if it divides the moving space into two subsets in which one of them we have an agent and in the other one or more targets. For example, consider the following level, in which “x” is an agent, “A” and “B” are fields, and “a” and “b” are the corresponding target positions:

+++++++++++++++++++++++++++++++++++++++++ xa b+ +++++ +++++++++++++++++++++++++++++++++ +AB + +++++ 

In this case, the goal position “a” is the cutting position, because if the field is placed there, the agent will not be able to reach goal “b”.

Can you suggest a quick algorithm for calculating cutting positions, and this can return the number of targets that each cutting position blocks?

Answer 1

What you call the cut position for your grid word is called the trimmed vertex or joint point in common graphs. From Wikipedia :

In particular, a clipped vertex is any vertex whose removal increases the number of connected components.

And a little further in the same article:

The classical sequential algorithm for computing binary components in a connected undirected graph of John Hopcroft and Robert Taryan (1973) [1] works in linear time and is based on depth search. This algorithm is also described as task 22-2 of introduction to algorithms (both the 2nd and 3rd editions).

Having identified biconnected components, defining articulation points is fairly simple: all nodes that are contained in more than one doubly connected component are articulation points.

Answer 2

You can put the area in an undirected graph, where each node is a map position, and two nodes are connected if the positions are adjacent to each other. Then you can mark these “cut positions” on the chart and see all the paths that will be locked by the box at the cut position.