Implan: Scalable Incremental Motion Planning for Multi-Robot Systems
Indranil Saha, Rattanachai Ramaithitima, Vijay Kumar, George Pappas, Sanjit Seshia

Citation
Indranil Saha, Rattanachai Ramaithitima, Vijay Kumar, George Pappas, Sanjit Seshia. "Implan: Scalable Incremental Motion Planning for Multi-Robot Systems". ICCPS 2016 conference, 11, April, 2016.

Abstract
We consider the collision-free motion planning problem for a group of robots using a library of motion primitives. One can model the motion planning problem as a boolean combination of linear arithmetic constraints, and solve those constraints using an off-the-shelf SMT solver to generate trajectories for the robots. However, the number of constraints that ensure collision avoidance among the robots grows quadratically with the number of robots, and SMT solvers cannot deal with a system with more than a few robots in a reasonable time. To cope with the complexity of the problem, we introduce an incremental algorithm where we divide the robots into small groups based on a priority assignment algorithm. The priority assignment algorithm assigns priorities to the robots in such a way that the robots do not block the cost-optimal trajectories of the other robots. While the priority assignment algorithm attempts to assign distinct priorities to the robots, the algorithm needs to assign the same priority to some robots due to the dependencies among themselves. The priority assignment algorithm includes the robots with the same priority in the same group. We then consider the robot groups one by one based on their priority and synthesize the trajectories of all the robots in a group together. While synthesizing the trajectories for the robots in one group, we consider the higher priority robots as dynamic obstacles, and introduce minimal delay to execute the cost-optimal trajectories to avoid collision with the higher priority robots. Thus, the incremental motion planning algorithm divides a hard SMT solving problem into a number of smaller SMT solving problems that can be efficiently solved using an SMT solver. We apply our method to synthesize trajectories for a group of quadrotors with complex dynamics. Experimental results show that we can synthesize trajectories for tens of robots with complex dynamics in a reasonable time.

Electronic downloads


Internal. This publication has been marked by the author for TerraSwarm-only distribution, so electronic downloads are not available without logging in.
Citation formats  
  • HTML
    Indranil Saha, Rattanachai Ramaithitima, Vijay Kumar, George
    Pappas, Sanjit Seshia. <a
    href="http://www.terraswarm.org/pubs/554.html"
    >Implan: Scalable Incremental Motion Planning for
    Multi-Robot Systems</a>, ICCPS 2016 conference, 11,
    April, 2016.
  • Plain text
    Indranil Saha, Rattanachai Ramaithitima, Vijay Kumar, George
    Pappas, Sanjit Seshia. "Implan: Scalable Incremental
    Motion Planning for Multi-Robot Systems". ICCPS 2016
    conference, 11, April, 2016.
  • BibTeX
    @inproceedings{SahaRamaithitimaKumarPappasSeshia16_ImplanScalableIncrementalMotionPlanningForMultiRobot,
        author = {Indranil Saha and Rattanachai Ramaithitima and
                  Vijay Kumar and George Pappas and Sanjit Seshia},
        title = {Implan: Scalable Incremental Motion Planning for
                  Multi-Robot Systems},
        booktitle = {ICCPS 2016 conference},
        day = {11},
        month = {April},
        year = {2016},
        abstract = {We consider the collision-free motion planning
                  problem for a group of robots using a library of
                  motion primitives. One can model the motion
                  planning problem as a boolean combination of
                  linear arithmetic constraints, and solve those
                  constraints using an off-the-shelf SMT solver to
                  generate trajectories for the robots. However, the
                  number of constraints that ensure collision
                  avoidance among the robots grows quadratically
                  with the number of robots, and SMT solvers cannot
                  deal with a system with more than a few robots in
                  a reasonable time. To cope with the complexity of
                  the problem, we introduce an incremental algorithm
                  where we divide the robots into small groups based
                  on a priority assignment algorithm. The priority
                  assignment algorithm assigns priorities to the
                  robots in such a way that the robots do not block
                  the cost-optimal trajectories of the other robots.
                  While the priority assignment algorithm attempts
                  to assign distinct priorities to the robots, the
                  algorithm needs to assign the same priority to
                  some robots due to the dependencies among
                  themselves. The priority assignment algorithm
                  includes the robots with the same priority in the
                  same group. We then consider the robot groups one
                  by one based on their priority and synthesize the
                  trajectories of all the robots in a group
                  together. While synthesizing the trajectories for
                  the robots in one group, we consider the higher
                  priority robots as dynamic obstacles, and
                  introduce minimal delay to execute the
                  cost-optimal trajectories to avoid collision with
                  the higher priority robots. Thus, the incremental
                  motion planning algorithm divides a hard SMT
                  solving problem into a number of smaller SMT
                  solving problems that can be efficiently solved
                  using an SMT solver. We apply our method to
                  synthesize trajectories for a group of quadrotors
                  with complex dynamics. Experimental results show
                  that we can synthesize trajectories for tens of
                  robots with complex dynamics in a reasonable time.},
        URL = {http://terraswarm.org/pubs/554.html}
    }
    

Posted by Indranil Saha on 6 May 2015.
Groups: tools

Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright.