Motion Planning(global path planning)アルゴリズムまとめ

目次

Journal memo

• Journal of Intelligent & Robotic Systems
• IEEE Transactions on Robotics
• Journal of Advanced Robotic Systems
• IJRR, International Journal of Robotics Research

比較論文

• A Review of Global Path Planning Methods for Occupancy Grid Maps Regardless of Obstacle Density
  • https://www.researchgate.net/publication/303501196_A_Review_of_Global_Path_Planning_Methods_for_Occupancy_Grid_Maps_Regardless_of_Obstacle_Density
  • 2016

    PRMはかなり人気のあるアルゴリズムカテゴリだが、アプリケーション空間によってはサイズが大きくなりすぎ、実行時間を短くできないという欠点がある

  • 評価指標の言及がある(3.1)
  • 評価環境の言及がある(3.2)

Check researcher

• Emmanouil Tsardoulias
  • ギリシャ、アリストテレス大学
  • https://scholar.google.gr/citations?user=icsof3YAAAAJ&hl=en
  • SLAM, Path Planning

A*

• A*
  • A Formal Basis for the Heuristic Determination of Minimum Cost Paths
    • https://ieeexplore.ieee.org/document/4082128
    • 1968
• LPA*(Lifelong Planning A*)
  • Incremental A*
    • https://pdfs.semanticscholar.org/bb81/c597a83a221e3594577686ae47ca05a8a091.pdf
    • 2001
    • Georgia Institude of Technology
  • Lifelong Planning A*
    • https://www.cs.cmu.edu/~maxim/files/aij04.pdf
    • 2005
• ARA* (Anytime Repairing A* )
  • ARA: Anytime A with Provable Bounds on Sub-Optimality
    • http://robots.stanford.edu/papers/Likhachev03b.pdf
    • 2003
    • CMU
• Hybrid A*
  • Practical Search Techniques in Path Planning for Autonomous Driving
    • https://ai.stanford.edu/~ddolgov/papers/dolgov_gpp_stair08.pdf
    • 2008
    • TRI & Stanford
  • Application of Hybrid A* to an Autonomous Mobile Robot for Path Planning in Unstructured Outdoor Environments
    • https://ieeexplore.ieee.org/abstract/document/6309512
    • 2012

D*

• D*(Dynamic A*)
  • Optimal and Efficient Path Planning for Partially-Known Environments
    • http://robotics.caltech.edu/~jwb/courses/ME132/handouts/Dstar_icra94.pdf
    • CMU, Anthony Stentz, 1994
• Focussed D*
  • The Focussed D* Algorithm for Real-Time Replanning
  • https://dl.acm.org/citation.cfm?id=1643113
  • CMU, Anthony Stentz,1995

• D* lite

  • D* lite
    • http://idm-lab.org/bib/abstracts/papers/aaai02b.pdf
    • CMU, Maxim Likhachev, GIT, Sven Koenig, 2002
  • Second version
    • https://www.cs.cmu.edu/~maxim/files/dlite_tro05.pdf
    • 2005

• Field D*

  • The Field D* Algorithm for Improved Path Planning and Replanning in Uniform and Non-Uniform Cost Environments
    • https://pdfs.semanticscholar.org/58f3/bc8c12ee8df30b3e9564fdd071e729408653.pdf
    • CMU, Dave Ferguson and Anthony Stentz, 2005
  • 3D Field D*: Improved Path Planning and Replanning in Three Dimensions
    • https://www.ri.cmu.edu/pub_files/pub4/carsten_joseph_2006_1/carsten_joseph_2006_1.pdf
    • IROS2006, Joseph Carsten∗, Dave Ferguson, and Anthony Stentz, CMU
• AD* (Anytime Dynamic A* )
  • Anytime Dynamic A*: An Anytime, Replanning Algorithm
    • http://www.cs.cmu.edu/~ggordon/likhachev-etal.anytime-dstar.pdf
    • CMU, Stanford, Maxim Likhachev, Dave Ferguson, Geoff Gordon, Anthony Stentz, Sebastian Thrun, 2005
• D*'s key person
  • Anthony Stentz, now he is Research Professor of Robotics at CMU
    • Google Scholar
    • https://scholar.google.co.jp/citations?hl=ja&user=cnFhxvMAAAAJ&view_op=list_works&sortby=pubdate

RRT

• RRT
  • Rapidly-Exploring Random Trees: A New Tool for Path Planning
  • http://msl.cs.uiuc.edu/~lavalle/papers/Lav98c.pdf
  • 1998
• Replanning with RRTs
  • https://www.ri.cmu.edu/pub_files/pub4/ferguson_david_2006_2/ferguson_david_2006_2.pdf
  • 2006, Anthony Stentz(D*の人)
• RRT-Connect
  • RRT-Connect: An Efficient Approach to Single-Query Path Planning
  • ICRA2000
  • https://www.cs.cmu.edu/afs/cs/academic/class/15494-s14/readings/kuffner_icra2000.pdf
• Bi-RRT
  • Offline and Online Evolutionary Bi-Directional RRT Algorithms for Efficient Re-Planning in Dynamic Environments
    • https://ieeexplore.ieee.org/abstract/document/4341761
    • 2007, ジョンズ・ホプキンズ大学,
• Cell-RRT
  • Cell-RRT: Decomposing the environment for better plan
    • https://ieeexplore.ieee.org/document/5354106
    • IROS2009
• T-RRT
  • Sampling-Based Path Planning on Configuration-Space Costmaps
    • Sampling-Based Path Planning on Configuration-Space Costmaps - IEEE Journals & Magazine
    • 2010
• RRT*
  • Sampling-based Algorithms for Optimal Motion Planning
    • https://arxiv.org/pdf/1105.1186.pdf
    • 2011
    • Sertac Karaman, MIT
      • Google Scholar
        • https://scholar.google.com/citations?hl=ja&user=Vu-Zb7EAAAAJ&view_op=list_works&sortby=pubdate
    • Emilio Frazzoli, MIT(航空宇宙工学の教授)
      • http://ares.lids.mit.edu/
      • Google Scholar
        • https://scholar.google.com/citations?user=8JGG3KcAAAAJ&hl=en
      • 今はETHにいるようだ。今はDynamic System and Controlを専門としている
        • https://idsc.ethz.ch/research-frazzoli.html
• LQR-RRT*
  • LQR-RRT*: Optimal sampling-based motion planning with automatically derived extension heuristics
  • ICRA2012
• kinodynamic RRT*
  • https://ieeexplore.ieee.org/document/6631299
  • ICRA2013
• RRT*-SMART
  • RRT-SMART: A Rapid Convergence Implementation of RRT
    • https://journals.sagepub.com/doi/10.5772/56718
    • 2013 Journal of Advanced Robotic Systems
• A scalable distributed RRT for motion planning
  • https://ieeexplore.ieee.org/document/6631304
  • ICRA2013, Texas A&M Univ
• Informed RRT
  • Informed RRT*: Optimal Sampling-based Path Planning Focused via Direct Sampling of an Admissible Ellipsoidal Heuristic
  • https://arxiv.org/abs/1404.2334
  • IROS2014
• BiRRT*
  • BI2RRT*: An Efficient Sampling-Based Path Planning Framework for Task-Constrained Mobile Manipulation
    • http://ais.informatik.uni-freiburg.de/publications/papers/burget16iros.pdf
    • IROS2016
    • IEEE link : https://ieeexplore.ieee.org/document/7759547
• RRT with kinematics constraints
  • TP-Space RRT - kinematic path planning of non-holonomic any-shape vehicles

    • https://journals.sagepub.com/doi/full/10.5772/60463

  • 2015, Journal of Advanced Robotic Systems
  • Kinematic Constraints Based Bi-directional RRT (KB-RRT) with Parameterized Trajectories for Robot Path Planning in Cluttered Environment
    • ICRA2019
• RRT's key person
  • Steven M. LaValle
    • Google Scholar
      • https://scholar.google.com/citations?hl=ja&user=72e5VYEAAAAJ&view_op=list_works&sortby=pubdate
    • Professor of Robotics and Virtual Reality, University of Oulu
    • 今はVRの研究がメイン？
• 応用例
  • Real-time Motion Planning with Applications to Autonomous Urban Driving
    • 2009, Emilio FrazzoliなどIEEE member
    • http://acl.mit.edu/papers/KuwataTCST09.pdf
    • DARPA Urban Challengeのレポート

PRM(Probabilistic roadmap)

• PRM
  • Probabilistic roadmaps for path planning in high-dimensional configuration spaces
    • https://ieeexplore.ieee.org/document/508439
    • http://www.cs.cmu.edu/~./motionplanning/papers/sbp_papers/PRM/prmbasic_01.pdf
    • 1996, Lydia E. Kavraki, Mark H. Overmars
• Lazy PRM
  • Path planning using lazy PRM
    • https://ieeexplore.ieee.org/document/844107
    • ICRA2000, L.E. Kavraki
• Hybrid PRM Sampling with a Cost-Sensitive Adaptive Strategy
  • Hybrid PRM Sampling with a Cost-Sensitive Adaptive Strategy - IEEE Conference Publication
  • ICRA2005, シンガポール国立大学
  • 環境に応じてサンプリング手法を変える、うまく組み合わせる手法の提案
• PRM*, k-PRM
  • Sampling-based Algorithms for Optimal Motion Planning
    • https://arxiv.org/pdf/1105.1186.pdf
    • 2011
• Lazy Toggle PRM: A single-query approach to motion planning
  • https://ieeexplore.ieee.org/document/6630904?reload=true&arnumber=6630904
  • ICRA2013, Texas A&M University
• サンプリング手法に関する分析論文
  • A comparative study of probabilistic roadmap planners. In: Workshop on the algorithmic foundations of robotics
    • 2002, Geraerts, R., Overmars,, オランダ-ユトレヒト大学, 計算幾何学が専門, Wikiあり、Google Scholar無し
  • Sampling Techniques for Probabilistic Roadmap Planners. Intelligent Autonomous Systems
    • 2004, Geraerts, R., Overmars,
• サンプリング手法
  • 以下参考
    • A Review of Global Path Planning Methods for Occupancy Grid Maps Regardless of Obstacle Density
      • Uniform Space Sampling
      • Random Space Sampling
      • Space Sampling with Halton Sequences
      • Uniform Incremental Space Sampling
• PRM's key preson
  • Lydia E. Kavraki
    • RICE大学教授。 Kavraki Lab. ロボティクス
    • OMPL(Open Motion Planning Library)のownner
    • http://www.kavrakilab.org/
    • Google Scholar
      • https://scholar.google.co.jp/citations?hl=ja&user=Q6pxNZYAAAAJ&view_op=list_works&sortby=pubdate

Roadmap Spanner

• 参考: Stronger Formal Guarantees for Practical Motion Planners | Pracsys Lab
  • ラトガース(RITGERS)大学, PRACSYS(Physics-aware Research on Autonomous Computational Systems)
• Sequential Roadmap Spanner(SRS)
  • 従来手法として、PRMのroadmap生成手法をそう呼称し、漸近的に最適解を求められる代わりにメモリ量や探索時間が伸びてしまう。それを改善する手法として下記のIncremental, Sparseアプローチがでてきた。
• Incremental Roadmap Spanner(IRS)
  • IRS
    • Asymptotically near-optimal is good enough for motion planning
      • http://www.isrr-2011.org/ISRR-2011/Program_files/Papers/Marble-ISRR-2011.pdf
      • 2011, James D. Marble and Kostas E. Bekris, ラトガース大学
  • IRS2
    • Towards small asymptotically near-optimal roadmaps
      • https://www.cs.rutgers.edu/~kb572/pubs/towards_small_optimal_roadmaps.pdf
      • ICRA2012
  • Tutorial on Motion Planning for Mobile Manipula3on, ICRA2013, ラトガース大学
    • https://moveit.ros.org/assets/pdfs/2013/icra2013tutorial/spanner_roadmaps_Bekris.pdf
• Sparse Roadmap Spanner(SPARS)
  • Sparse Roadmap Spanners, 2012
    • https://www.cs.rutgers.edu/~kb572/pubs/sparse_roadmap_spanner.pdf
    • Andrew Dobson, Athanasios Krontiris and Kostas E. Bekris
  • Improving Sparse Roadmap Spanners, ICRA2013
    • https://www.cs.rutgers.edu/~kb572/pubs/spars2.pdf
    • Andrew Dobson and Kostas E. Bekris
• KSR
• K-Order Surrounding Roadmaps Path Planner for Robot Path Planning
• https://www.semanticscholar.org/paper/K-Order-Surrounding-Roadmaps-Path-Planner-for-Robot-Li-Li/6108a8ea29bf430e52308b79b4e8dbe9c2ec473e
• Journal of Intelligent and Robotic Systems 2014

Visibility Graph

• An algorithm for planning collision-free paths among polyhedral obstacles
  • http://lis.csail.mit.edu/pubs/tlp/collision-free-planning-cacm.pdf
  • IBM Thomas J. Watson Research Center
  • 1979

Voronoi Digram

• Voronoi diagram in optimal path planning
  • https://ieeexplore.ieee.org/document/4276103
  • カルガリー大学
  • ISVD2007(International Symposium on Voronoi Diagrams)
  • なお、ISVDは2013年が最後の開催日となっているようだ。2014年で延期となってそれ以来未開催
    • http://voronoi.hanyang.ac.kr/isvd2014/
• Path planning for mobile robot navigation using voronoi diagram and fast marching
  • https://ieeexplore.ieee.org/document/4058742
  • IROS2006
  • マドリード・カルロス三世大学

Stochastic path planning / trajectory optimiser (= functional gradient path planning ?)

• Stochastic Functional Gradient for Motion Planning in Continuous Occupancy Maps
• https://arxiv.org/pdf/1703.00194.pdf
• ICRA2017, Gilad Francis, Lionel Ott and Fabio Ramos
• Introductionの入りが超微妙...

  there are no trajectory optimiser implementations for path planning using occupancy maps we present a new planning paradigm using occupancy maps. We utilise the recently introduced Hilbert maps [2] instead of OGMs

• OGMを使った経路計画用の軌道最適化のアルゴリズムがないと言っているが、さすがにあるでしょ...
• それからOGMを使った軌道最適化について提案があるのかと思いきや、使わないんかい.
• path planner based on a Gaussian Process (GP) path representationの提案
• Fabio Ramos
  • Professor in machine learning and robotics, University of Sydney
  • Nvidiaのポジションもあるらしい
  • https://scholar.google.com.au/citations?user=T_mJiHoAAAAJ&hl=en
• Fast Stochastic Functional Path Planning in Occupancy Maps
  • https://www.cs.unm.edu/amprg/Workshops/MLPC18/submissions/paper_8.pdf

Trajectory generator

• The Trajectory Parameter Space (TP-Space): A New Space Representation for Non-Holonomic Mobile Robot Reactive Navigation

  • The Trajectory Parameter Space (TP-Space): A New Space Representation for Non-Holonomic Mobile Robot Reactive Navigation - IEEE Conference Publication

  • IROS2006
  • TP-Space, PTG(parameterized trajectory generator)という概念のoriginal

• Dubins path

  • On Curves of Minimal Length with a Constraint on Average Curvature, and with Prescribed Initial and Terminal Positions and Tangents

  • https://www.jstor.org/stable/2372560?seq=1#page_scan_tab_contents

  • 1957

• Reeds Shepp path

  • OPTIMAL PATHS FOR A CAR THAT GOES BOTH FORWARDS AND BACKWARDS http://sector3.imm.uran.ru/shepp/Reeds_Shepp_trunk.pdf
  • 1994

  • http://planning.cs.uiuc.edu/node822.html

• Ackermann steering geometry

  • 1954 アッカーマン・ジャントー - Wikipedia

https://ieeexplore.ieee.org/document/5477164