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