Team for Research in
Ubiquitous Secure Technology

Citation
Mikhail Lisovich, Maxim Likhachev. "Joint State-Space Planning: A Practical Algorithm for the Multiple Path Consensus Problem". 2010 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2010), 2010.

Abstract
We consider the multiple-path consensus (MPC) problem, where multiple agents coupled by time-parametrized distance constraints navigate together in a cluttered environment. We motivate the problem, determine it to be NP complete, then present various potential approaches to its solution, including a previously developed potentials-like iterative algorithm and an integer programming framework. After considering the advantages and disadvantages of these methods, we choose to develop the joint state-space planning (JSSP) approach. We show that with the correct formulation, the problem is amenable to JSSP for practically-sized instances. We give a iterative search algorithm, which generates a sequence of strictly-improving near-optimal solutions, and which is provably correct, complete, and optimal. We then validate the algorithm through simulation, showing rapid convergence for a broad range of problem instances. The paper concludes with a discussion of design choices to ensure good performance for live experiments, as well as a survey of future work.

Electronic downloads

• HTML

  Mikhail Lisovich, Maxim Likhachev. <a
  href="http://www.truststc.org/pubs/661.html"
  >Joint State-Space Planning: A Practical Algorithm for
  the Multiple Path Consensus Problem</a>, 2010 IEEE/RSJ
  International Conference on Intelligent Robots and Systems  
  (IROS 2010), 2010.

• Plain text

  Mikhail Lisovich, Maxim Likhachev. "Joint State-Space
  Planning: A Practical Algorithm for the Multiple Path
  Consensus Problem". 2010 IEEE/RSJ International
  Conference on Intelligent Robots and Systems   (IROS 2010),
  2010.

• BibTeX

  @inproceedings{LisovichLikhachev10_JointStateSpacePlanningPracticalAlgorithmForMultiple,
      author = {Mikhail Lisovich and Maxim Likhachev},
      title = {Joint State-Space Planning: A Practical Algorithm
                for the Multiple Path Consensus Problem},
      booktitle = {2010 IEEE/RSJ International Conference on
                Intelligent Robots and Systems   (IROS 2010)},
      year = {2010},
      abstract = {We consider the multiple-path consensus (MPC)
                problem, where multiple agents coupled by
                time-parametrized distance constraints navigate
                together in a cluttered environment. We motivate
                the problem, determine it to be NP complete, then
                present various potential approaches to its
                solution, including a previously developed
                potentials-like iterative algorithm and an integer
                programming framework. After considering the
                advantages and disadvantages of these methods, we
                choose to develop the joint state-space planning
                (JSSP) approach. We show that with the correct
                formulation, the problem is amenable to JSSP for
                practically-sized instances. We give a iterative
                search algorithm, which generates a sequence of
                strictly-improving near-optimal solutions, and
                which is provably correct, complete, and optimal.
                We then validate the algorithm through simulation,
                showing rapid convergence for a broad range of
                problem instances. The paper concludes with a
                discussion of design choices to ensure good
                performance for live experiments, as well as a
                survey of future work.},
      URL = {http://www.truststc.org/pubs/661.html}
  }
  

Posted by Mikhail Lisovich on 28 Mar 2010.
For additional information, see the Publications FAQ or contact webmaster at www truststc org.