2
$\begingroup$

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: Worm A should get to its goal state A and Worm B to its goal state B

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 RIGHT-RIGHT-RIGHT-RIGHT-RIGHT-RIGHT-UP-UP-UP.

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: XXB^X^^ etc.

Improve this question
$\endgroup$
3
  • $\begingroup$ Your questions are interesting, but, please, *ask one question per post, even though they are somehow related. If you have $N$ questions, create $N$ posts. So, please, try to simplify this post and ask only one question. $\endgroup$
    – nbro
    Commented May 7, 2020 at 17:02
  • $\begingroup$ @nbro Thank you for reaching this and commenting. I didn't want to look like a spam, that's why I asked these questions in one post. How ever, I'll have this in mind for asking questions in the future :) $\endgroup$
    – anthino12
    Commented May 7, 2020 at 17:41
  • $\begingroup$ Please, try to simplify this question is a little bit more. I couldn't even read it until the end because it contains too much information for my brain to process :) $\endgroup$
    – nbro
    Commented May 7, 2020 at 22:11

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .