1
$\begingroup$

a formulation on an example:

let's have on a grid:

  • a position of a bee queen Q (source node),
  • a set of positions of free cells to lay an egg E (destination nodes),
  • and a set of positions with worker bees W (moveable obstacles).

the queen and workers can move to 4 orthogonally neighboring cells (left, right, up, down)

 e  w
e ww
 w Q

the task is to find an efficient sequence of moves for the queen and workers to lay the queen's egg.
(what is an efficient algorithm to find the shortest sequence of moves for queen and workers?)


obviously, if the obstacles were immovable, i would use a simple BFS or A*.

if the obstacles W or destinations E were moveable but not by me, i would use other pathfinders like D*.

but i'm in control of moving the workers, so one of the solutions is:

  • queen moves left
 e  w
e ww
 wQ.
  • worker gives her way
 ew w
e .w
 wQ 
  • and then 3 moves for the queen:
 ew w
Q..w
 w. 

there is no shorter path

$\endgroup$
3
  • $\begingroup$ Can you identify the source where you first encountered this, and credit that source? Thanks! $\endgroup$
    – D.W.
    Commented Sep 24, 2022 at 21:06
  • 1
    $\begingroup$ Can you state what your question is, explicitly? We're a question-and-answer site, so it's important to ask a specific question in the post. $\endgroup$
    – D.W.
    Commented Sep 24, 2022 at 21:07
  • $\begingroup$ the problem has no source. i've made it up and could not find something like this here on SE and elsewhere. $\endgroup$
    – Dan Oak
    Commented Sep 24, 2022 at 21:39

1 Answer 1

1
$\begingroup$

This remains a reachability problem, but now with a larger statespace.

The state of the system is the location of the queen and of all the workers. You have a transition from state $s$ to state $t$ if $t$ can be reached from $s$ in a single step (i.e., the queen moves one step, or one worker moves one step). The goal is now to find the shortest path from the initial state to a goal state.

This is a statespace reachability problem, and it can be solved with any algorithm for statespace exploration. For instance, you can use BFS, or you can use A* with an appropriate heuristic function.

I don't know what is the best heuristic to use with A*. A simple heuristic is to use the Manhattan distance from from the queen to the nearest egg (or, equivalently, the length of the shortest path if there were no workers). A better heuristic might be to find the shortest path from the queen to any egg, where only the queen can move, and it costs 1 for the queen to move to an empty square and it costs 2 for the queen to move to a square that has a worker in it (now the queen is allowed to occupy the same square as a worker, solely for purposes of computing this heuristic). Perhaps you can find a better heuristic.

I don't know whether there is any algorithm that can be guaranteed to be efficient in all cases. In the worst case, there can be exponentially many possible states, so naive statespace exploration might be very inefficient, in the worst case.

$\endgroup$
2
  • $\begingroup$ the heuristic you described sounds promising, but also it feels very computationally heavy. i'm thinking maybe about finding a path as if there were no workers, and then for every worker on the way do some stuff to try to "clear" the found path. feels like there is some recursive nature to such "clearing" $\endgroup$
    – Dan Oak
    Commented Sep 24, 2022 at 22:10
  • $\begingroup$ @DanOak, I can imagine there could well be a better solution. Good luck! I hope you'll report back if you find a better solution! $\endgroup$
    – D.W.
    Commented Sep 25, 2022 at 0:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.