Body: <p>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:
  <a href="https://i.sstatic.net/wlKP4.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/wlKP4.png" alt="Worm A should get to its goal state A and Worm B to its goal state B"></a></p>
  
  <p>If we had only Worm B, the optimal cost from starting position to the goal position would be <code>9</code>, since one action costs <code>1</code> and it'd follow the path <code>RIGHT-RIGHT-RIGHT-RIGHT-RIGHT-RIGHT-UP-UP-UP</code>.</p>
  
  <p>My question is, if we have two worms, like in the picture, the optimal cost would be <code>9 + optimal cost for Worm A</code>?</p>
  
  <p>Also, strictly for this problem with 2 agents, if we use Manhattan distance as a heuristic for <strong>one agent</strong>, would it be admissible if we take the <strong>average of Worm A and B heuristics</strong> for a problem with <strong>two agents</strong>? </p>
  
  <p>Another question, I know for a fact that <strong>sum of two admissible heuristics</strong> won't be admissible for one agent but would it be for the problem with <strong>two agents</strong>?</p>
  
  <p>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.</p>
  
  <p>For example, if we have something like <code>B^^^X^^^</code>, where B is the Worm B, <code>^</code> is an <strong>available</strong> <strong>field</strong> and <code>X</code> is a <strong>wall</strong>, after one RIGHT action it'll look like <code>XB^^X^^</code>, after one more RIGHT: <code>XXB^X^^</code> etc.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-07T17:02:50.083Z
Comments.Text: 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.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-07T17:41:34.037Z
Comments.Text: @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 :)
Comments.UserDisplayName: anthino12
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-07T22:11:48.037Z
Comments.Text: 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 :)
Comments.UserDisplayName: nbro
Tags: <heuristics><multi-agent-systems><a-star>
Title: How does heuristic work with multiple agents?
UserDisplayName: anthino12
ThreadText: # How does heuristic work with multiple agents?
  
  (Asked by: username_0 on 2020-05-07)
  
  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](https://i.sstatic.net/wlKP4.png)](https://i.sstatic.net/wlKP4.png)
  
  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.
  
  **Tags:** heuristics, multi-agent-systems, a-star
  
  > **Comments:**
  > **username_1**: 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.  
  > **username_0**: @username_1 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 :)  
  > **username_1**: 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 :)  
  
  ---
  
  ## 0 answers
  
  