Dynamic DEC-LOS-RRT: Dynamic Decentralized Line of Sight Path Planning for Multi-Agents

By Saahil Parikh and Yi Wang
The need for swarms of intellegent robots is becoming ever more prevalent as the world adopts driverless cars, automated delivery vehicles and search and rescue drones.

Challenges

However, there exist many algorithmic challenges involving,

  • Communication constraints
  • Fleets in large scale
  • Complex environment
  • Vehicle Dynamics

    • Our reseach deals with the question: How do we ensure the safety of multi-agent motion planning in situations where agents are unable to constantly contact each other and satisfy the dynamic constraint at each iteration?
    Algorithms pertaining to multi-agent motion planning and how unable to constantly contact each other have been proposed. Our reseach extends proposed solutions to agents with dynamic constraints. See below for relevant links to those previously proposed solutions.

    DMA-RRT: V. R. Desaraju and J. P. How, "Decentralized path planning for multi-agent teams in complex environments using rapidly-exploring random trees," 2011 IEEE International Conference on Robotics and Automation, 2011, pp. 4956-4961, doi: 10.1109/ICRA.2011.5980392.

    DEC-LOS-RRT: arXiv:2203.02609

    Our solution draws from the DEC-LOS-RRT idea of expanding each obstacle in the enviornment by the infinity norm with a factor of delta.
    The idea is to define concentric circles as a "speed limit" for agents in the environment.
    We can see that the worst case scenario for two line of sight robots is at exactly 2𝛿 from impact.
    Deriving the maximum environment safe velocity
    \[\begin{aligned} V_{f}^{2} & = V_{0}^{2} + 2a_{max}\Delta{x} \\ 0 & = V_{0}^{2} + 2a_{max}\Delta{x} \\ V_{0} & = \sqrt{2a_{max}\Delta{x}} \\ & = \sqrt{4a_{max}\delta} \\ & = 2\sqrt{a_{max}\delta} \end{aligned} \] or with a minimum distance between agents \[\begin{aligned} V_{0} & = \sqrt{2a_{max}\Delta{x}} \\ & = \sqrt{2a_{max}(2\delta-\epsilon/2)} \\ & = \sqrt{4a_{max}\delta-a_{max}\epsilon} \end{aligned} \]
    Graphing the velocity function.
    \[\max(2\sqrt{a_{max}\delta}, \sqrt{2a_{max}\Delta{x}})\]
    Putting multiple edges in the enviornment.
    \[\min_{edges}(\max(2\sqrt{a_{max}\delta}, \sqrt{2a_{max}\Delta{x}}))\]
    Depictions of robot.
    Who are we?
    Saahil Parikh: 3rd year undergraduate with intrests in path planning and controls.
    Killen Wang: 3rd year undergraduate
    Check out the code here