Optimal Temporal Logic Planning in Probabilistic Semantic Maps
Jie Fu, Nikolay A. Atanasov, Ufuk Topcu, George Pappas

Citation
Jie Fu, Nikolay A. Atanasov, Ufuk Topcu, George Pappas. "Optimal Temporal Logic Planning in Probabilistic Semantic Maps". IEEE International Conference on Robotics and Automation, 16, May, 2016.

Abstract
This paper considers robot motion planning under temporal logic constraints in probabilistic maps obtained by semantic simultaneous localization and mapping (SLAM). The uncertainty in a map distribution presents a great challenge for obtaining correctness guarantees with respect to the linear temporal logic (LTL) specification. We show that the problem can be formulated as an optimal control problem in which both the semantic map and the logic formula evaluation are stochastic. Our first contribution is to reduce the stochastic control problem for a subclass of LTL to a deterministic shortest path problem by introducing a confidence parameter delta. A robot trajectory obtained from the deterministic problem is guaranteed to have minimum cost and to satisfy the logic specification in the true environment with probability delta. Our second contribution is to design an admissible heuristic function that guides the planning in the deterministic problem towards satisfying the temporal logic specification. This allows us to obtain an optimal and very efficient solution using the A* algorithm. The performance and correctness of our approach are demonstrated in a simulated semantic environment using a differential-drive robot.

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

  Jie Fu, Nikolay A. Atanasov, Ufuk Topcu, George Pappas.
  <a
  href="http://www.terraswarm.org/pubs/620.html"
  >Optimal Temporal Logic Planning in Probabilistic
  Semantic Maps</a>, IEEE International Conference on
  Robotics and Automation, 16, May, 2016.

• Plain text

  Jie Fu, Nikolay A. Atanasov, Ufuk Topcu, George Pappas.
  "Optimal Temporal Logic Planning in Probabilistic
  Semantic Maps". IEEE International Conference on
  Robotics and Automation, 16, May, 2016.

• BibTeX

  @inproceedings{FuAtanasovTopcuPappas16_OptimalTemporalLogicPlanningInProbabilisticSemanticMaps,
      author = {Jie Fu and Nikolay A. Atanasov and Ufuk Topcu and
                George Pappas},
      title = {Optimal Temporal Logic Planning in Probabilistic
                Semantic Maps},
      booktitle = {IEEE International Conference on Robotics and
                Automation},
      day = {16},
      month = {May},
      year = {2016},
      abstract = {This paper considers robot motion planning under
                temporal logic constraints in probabilistic maps
                obtained by semantic simultaneous localization and
                mapping (SLAM). The uncertainty in a map
                distribution presents a great challenge for
                obtaining correctness guarantees with respect to
                the linear temporal logic (LTL) specification. We
                show that the problem can be formulated as an
                optimal control problem in which both the semantic
                map and the logic formula evaluation are
                stochastic. Our first contribution is to reduce
                the stochastic control problem for a subclass of
                LTL to a deterministic shortest path problem by
                introducing a confidence parameter delta. A robot
                trajectory obtained from the deterministic problem
                is guaranteed to have minimum cost and to satisfy
                the logic specification in the true environment
                with probability delta. Our second contribution is
                to design an admissible heuristic function that
                guides the planning in the deterministic problem
                towards satisfying the temporal logic
                specification. This allows us to obtain an optimal
                and very efficient solution using the A*
                algorithm. The performance and correctness of our
                approach are demonstrated in a simulated semantic
                environment using a differential-drive robot.},
      URL = {http://terraswarm.org/pubs/620.html}
  }
  

Posted by Nikolay A. Atanasov on 26 Sep 2015.
Groups: services