I have a question for heuristic search with multiple agents. I know how heuristic search works with one agent (ex. one Pacman) but I don't really understand it with multiple agents. Let's say we have this problem where Worm A has to get to its goal state A and Worm B to B, knowing that the agents can move only in vertical and horizontal way:
If we had only Worm B, the optimal cost from starting position to the goal position would be
9, since one action costs
1 and it'd follow the path
My question is, if we have two worms, like in the picture, the optimal cost would be
9 + optimal cost for Worm A?
Also, strictly for this problem with 2 agents, if we use Manhattan distance as a heuristic for one agent, would it be admissible if we take the average of Worm A and B heuristics for a problem with two agents?
Another question, I know for a fact that sum of two admissible heuristics won't be admissible for one agent but would it be for the problem with two agents?
These two worms are dependent of each other. How? If one worm moves from position X to Y, the position X is marked as a wall and is not an available field to move in. So if one worm has been in a specific position, that position is no more free for moving in.
For example, if we have something like
B^^^X^^^, where B is the Worm B,
^ is an available field and
X is a wall, after one RIGHT action it'll look like
XB^^X^^, after one more RIGHT: