Question:
I am working on a pathfinding problem where two agents must navigate separate mazes simultaneously using the same sequence of movement instructions. Each maze is an n × m grid, and both agents start at (0,0) and need to reach (n-1, m-1).
Rules:
- Each instruction (↑, ↓, ←, →) moves both agents.
- If an agent encounters a wall, they stay in place while the other may continue.
- If an agent reaches the goal, they stay there until the other arrives.
- Some mazes contain pits: stepping into one resets the agent to (0,0).
The challenge is that both agents must follow the same instructions, which significantly limits their movement options. A brute-force search is infeasible for large n, m due to the exponential search space.
My Question:
What are efficient strategies to compute the shortest possible sequence of instructions that gets both agents to the goal?
