無人車運動規劃的52篇文章
本來想湊出一百篇的，後來發現有些工作雖然寫得也比較完備，但是開創性並不大，只是一個良好的應用型文章，後來就只列出了這51篇。當然，為了搞懂這些文章，閱讀一些闡述詳細的應用型文章是少不了的。
[1] E. W. Dijkstra, 「A note on two problems in connexion with graphs,」 Numerische Mathematik, vol. 1, no. 1, pp. 269–271, Dec. 1959.
遠古大神E.W. Dijkstra開發的Dijkstra演算法，在拓撲圖，柵格圖，lattice圖中搜索都有不錯的效果。
[2] P. E. Hart, N. J. Nilsson, and B. Raphael, 「A Formal Basis for the Heuristic Determination of Minimum Cost Paths,」 IEEE Transactions on Systems Science and Cybernetics, vol. 4, no. 2, pp. 100–107, Jul. 1968.
A* 演算法，在Dijkstra的代價函數里增加了啟發函數，速度快，保證最優，但很多時候因為啟發值的問題並不能適用很多問題。
[3] Bellman R. Dynamic programming[J]. Science, 1966, 153(3731): 34-37.
Bellman的動態規劃，在拓撲圖和最優控制中應用很廣。
[4] A. Stentz, 「Optimal and efficient path planning for partially-known environments,」 in Robotics and Automation, 1994. Proceedings., 1994 IEEE International Conference on, 1994, pp. 3310–3317.
[5] A. Stentz, 「The Focussed D* Algorithm for Real-Time Replanning,」 p. 8.
D*演算法。
[6] D. Ferguson and A. Stentz, 「Using interpolation to improve path planning: The Field D* algorithm,」 J. Field Robotics, vol. 23, no. 2, pp. 79–101, Feb. 2006.
Field D*演算法。
[7] S. Koenig, M. Likhachev, and D. Furcy, 「Lifelong Planning A?,」 Artificial Intelligence, vol. 155, no. 1–2, pp. 93–146, May 2004.
LPA*演算法。
[8] S. Koenig and M. Likhachev, 「Improved fast replanning for robot navigation in unknown terrain,」 in Proceedings 2002 IEEE International Conference on Robotics and Automation (Cat. No.02CH37292), 2002, vol. 1, pp. 968–975 vol.1.
[9] S. Koenig and M. Likhachev, 「Fast replanning for navigation in unknown terrain,」 IEEE Trans. Robot., vol. 21, no. 3, pp. 354–363, Jun. 2005.
D* Lite演算法。
[10] A. Kelly and B. Nagy, 「Reactive Nonholonomic Trajectory Generation via Parametric Optimal Control,」 The International Journal of Robotics Research, vol. 22, no. 7–8, pp. 583–601, Jul. 2003.
這篇文章非常經典，用spiral連接兩個狀態。下面是我寫的一些想法。
小鄔：模型預測軌跡生成與lattice
[11] T. M. Howard and A. Kelly, 「Optimal Rough Terrain Trajectory Generation for Wheeled Mobile Robots,」 The International Journal of Robotics Research, vol. 26, no. 2, pp. 141–166, Feb. 2007.
[12] T. M. Howard, C. J. Green, A. Kelly, and D. Ferguson, 「State space sampling of feasible motions for high-performance mobile robot navigation in complex environments,」 Journal of Field Robotics, vol. 25, no. 6–7, pp. 325–345, Jun. 2008.
這兩篇文章叫做模型預測軌跡生成，也是受到spiral的啟發。
[13] D. Dolgov, S. Thrun, M. Montemerlo, and J. Diebel, 「Practical Search Techniques in Path Planning for Autonomous Driving,」 p. 6.
[14] D. Dolgov, S. Thrun, M. Montemerlo, and J. Diebel, 「Path Planning for Autonomous Vehicles in Unknown Semi-structured Environments,」 The International Journal of Robotics Research, vol. 29, no. 5, pp. 485–501, Apr. 2010.
[15] M. Montemerlo et al., 「Junior: The Stanford entry in the Urban Challenge,」 Journal of Field Robotics, vol. 25, no. 9, pp. 569–597, Sep. 2008.
斯坦福在DARPPA挑戰賽期間開發的演算法。Hybrid A*及其優化。
[16] C. Urmson et al., 「Autonomous driving in urban environments: Boss and the Urban Challenge,」 Journal of Field Robotics, vol. 25, no. 8, pp. 425–466, Aug. 2008.
[17] D. Ferguson, T. M. Howard, and M. Likhachev, 「Motion planning in urban environments,」 Journal of Field Robotics, vol. 25, no. 11–12, pp. 939–960, Nov. 2008.
[18] J. Leonard et al., 「A perception-driven autonomous urban vehicle,」 Journal of Field Robotics, vol. 25, no. 10, pp. 727–774, Oct. 2008.
MIT 在DARPPA期間用的演算法。 RRT。
[19] D. Fox, W. Burgard, and S. Thrun, 「The dynamic window approach to collision avoidance,」 IEEE Robotics & Automation Magazine, vol. 4, no. 1, pp. 23–33, Mar. 1997.
動態窗口法，是控制空間採樣比較代表性的演算法，也有許多人分為反應式運動規劃演算法一類。
[20] L. E. Kavraki, P. Svestka, J.-C. Latombe, and M. H. Overmars, 「Probabilistic roadmaps for path planning in high-dimensional configuration spaces,」 IEEE Transactions on Robotics and Automation, vol. 12, no. 4, pp. 566–580, Aug. 1996.
狀態空間隨機採樣PRM演算法。
[21] LaValle S M. Rapidly-exploring random trees: A new tool for path planning[J]. 1998.
狀態空間隨機採樣RRT演算法。
[22] Y. Kuwata, J. Teo, G. Fiore, S. Karaman, E. Frazzoli, and J. P. How, 「Real-Time Motion Planning With Applications to Autonomous Urban Driving,」 IEEE Transactions on Control Systems Technology, vol. 17, no. 5, pp. 1105–1118, Sep. 2009.
[23] S. Karaman and E. Frazzoli, 「Optimal kinodynamic motion planning using incremental sampling-based methods,」 in 49th IEEE Conference on Decision and Control (CDC), Atlanta, GA, USA, 2010, pp. 7681–7687.
狀態空間隨機採樣RRT*演算法。
[24] O. Khatib, 「Real-time obstacle avoidance for manipulators and mobile robots,」 in Robotics and Automation. Proceedings. 1985 IEEE International Conference on, 1985, vol. 2, pp. 500–505.
人工勢場法。
CMU
卡耐基梅隆大學的人才源源不斷，規劃領域的許多常見演算法都來自CMU，可見CMU的機器人學有多強悍。一些博士論文更是經典。
[25] M. McNaughton, C. Urmson, J. M. Dolan, and J.-W. Lee, 「Motion planning for autonomous driving with a conformal spatiotemporal lattice,」 in 2011 IEEE International Conference on Robotics and Automation, Shanghai, China, 2011, pp. 4889–4895.
[26] W. Xu, J. Wei, J. M. Dolan, H. Zhao, and H. Zha, 「A real-time motion planner with trajectory optimization for autonomous vehicles,」 in 2012 IEEE International Conference on Robotics and Automation, 2012, pp. 2061–2067.
降維，採樣，優化
[27] T. Gu, J. Snider, J. M. Dolan, and J. Lee, 「Focused Trajectory Planning for autonomous on-road driving,」 in 2013 IEEE Intelligent Vehicles Symposium (IV), Gold Coast City, Australia, 2013, pp. 547–552.
降維，搜索，再次搜索
德國KIT開發的演算法
[28] S. Kammel et al., 「Team AnnieWAY』s autonomous system for the 2007 DARPA Urban Challenge,」 J. Field Robotics, vol. 25, no. 9, pp. 615–639, Sep. 2008.
[29] J. Ziegler and C. Stiller, 「Spatiotemporal state lattices for fast trajectory planning in dynamic on-road driving scenarios,」 in 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems, St. Louis, MO, USA, 2009, pp. 1879–1884.
[30] J. Ziegler and C. Stiller, 「Fast collision checking for intelligent vehicle motion planning,」 in 2010 IEEE Intelligent Vehicles Symposium, 2010, pp. 518–522.
[31] M. Werling, J. Ziegler, S. Kammel, and S. Thrun, 「Optimal trajectory generation for dynamic street scenarios in a Frenét Frame,」 in 2010 IEEE International Conference on Robotics and Automation, Anchorage, AK, 2010, pp. 987–993.
這一篇經典，一個三維規劃問題變成兩個二維採樣問題。
[32] M. Werling, S. Kammel, J. Ziegler, and L. Gr?ll, 「Optimal trajectories for time-critical street scenarios using discretized terminal manifolds,」 The International Journal of Robotics Research, vol. 31, no. 3, pp. 346–359, Mar. 2012.
[33] J. Ziegler, P. Bender, T. Dang, and C. Stiller, 「Trajectory planning for Bertha — A local, continuous method,」 in 2014 IEEE Intelligent Vehicles Symposium Proceedings, 2014, pp. 450–457.
這一篇非常經典，我們怎麼處理非凸障礙物，作者引入了行駛通道和lanelet，然後時間序列化，然後SQP優化[x,y].這種處理激發了很多後來的工作。
[34] J. Ziegler et al., 「Making Bertha Drive—An Autonomous Journey on a Historic Route,」 IEEE Intelligent Transportation Systems Magazine, vol. 6, no. 2, pp. 8–20, Summer 2014.
[35] M. Kelly, 「An Introduction to Trajectory Optimization: How to Do Your Own Direct Collocation,」 SIAM Rev., vol. 59, no. 4, pp. 849–904, Jan. 2017.
[36] N. Ratliff, M. Zucker, J. A. Bagnell, and S. Srinivasa, 「CHOMP: Gradient optimization techniques for efficient motion planning,」 in 2009 IEEE International Conference on Robotics and Automation, 2009, pp. 489–494.
[37] M. Zucker et al., 「CHOMP: Covariant Hamiltonian optimization for motion planning,」 The International Journal of Robotics Research, vol. 32, no. 9–10, pp. 1164–1193, Aug. 2013.
[38] P. Bender, J. Ziegler, and C. Stiller, 「Lanelets: Efficient map representation for autonomous driving,」 in 2014 IEEE Intelligent Vehicles Symposium Proceedings, 2014, pp. 420–425.
韓國漢陽大學的運動規劃
[39] K. Chu, M. Lee, and M. Sunwoo, 「Local Path Planning for Off-Road Autonomous Driving With Avoidance of Static Obstacles,」 IEEE Transactions on Intelligent Transportation Systems, vol. 13, no. 4, pp. 1599–1616, Dec. 2012.
[40] J. Kim, K. Jo, W. Lim, M. Lee, and M. Sunwoo, 「Curvilinear-Coordinate-Based Object and Situation Assessment for Highly Automated Vehicles,」 IEEE Transactions on Intelligent Transportation Systems, vol. 16, no. 3, pp. 1559–1575, Jun. 2015.
這兩篇比較有新意的是怎麼處理參考線問題，寫得很詳細。怎麼分段，怎麼弧長參數化，可以參考[49][50][51], 也可以去OPENDRIVE官網去看看他們怎麼處理參考線問題的。
[41] J. Kim and D. Kum, 「Collision Risk Assessment Algorithm via Lane-Based Probabilistic Motion Prediction of Surrounding Vehicles,」 IEEE Transactions on Intelligent Transportation Systems, vol. 19, no. 9, pp. 2965–2976, Sep. 2018.
[42] W. Lim, S. Lee, M. Sunwoo, and K. Jo, 「Hierarchical Trajectory Planning of an Autonomous Car Based on the Integration of a Sampling and an Optimization Method,」 IEEE Transactions on Intelligent Transportation Systems, vol. 19, no. 2, pp. 613–626, Feb. 2018.
這一篇也是解耦，先搜索再優化。
伯克利的運動規劃
[43] C. Liu, C. Lin, Y. Wang, and M. Tomizuka, 「Convex feasible set algorithm for constrained trajectory smoothing,」 in 2017 American Control Conference (ACC), 2017, pp. 4177–4182.
[44] C. Liu, W. Zhan, and M. Tomizuka, 「Speed profile planning in dynamic environments via temporal optimization,」 in 2017 IEEE Intelligent Vehicles Symposium (IV), 2017, pp. 154–159.
[45] C. Liu, C.-Y. Lin, and M. Tomizuka, 「The Convex Feasible Set Algorithm for Real Time Optimization in Motion Planning,」 SIAM Journal on Control and Optimization, vol. 56, no. 4, pp. 2712–2733, Jan. 2018.
對於一個三維規劃問題，建模為一個小的凸可行域優化問題。
[46] J. Chen, C. Liu, and M. Tomizuka, 「FOAD: Fast Optimization-based Autonomous Driving Motion Planner,」 in 2018 Annual American Control Conference (ACC), 2018, pp. 4725–4732.
[47] J. Chen, W. Zhan, and M. Tomizuka, 「Autonomous Driving Motion Planning with Constrained Iterative LQR,」 IEEE Transactions on Intelligent Vehicles, pp. 1–1, 2019.
百度Apollo
[48] Fan H. et al., 「Baidu Apollo EM Motion Planner,」 Jul. 2018.
這一篇將一個三維問題解耦為兩個二維問題，然後分別做搜索和優化。和xuwenda2012年的這一篇工作思路較像。
FRENET frame
[49] Wang H, Kearney J, Atkinson K. Robust and efficient computation of the closest point on a spline curve[C]//Proceedings of the 5th International Conference on Curves and Surfaces. 2002: 397-406.
[50] Wang H, Kearney J, Atkinson K. Arc-length parameterized spline curves for real-time simulation[C]//Proc. 5th International Conference on Curves and Surfaces. 2002, 387396.
[51] Hu X, Chen L, Tang B, et al. Dynamic path planning for autonomous driving on various roads with avoidance of static and moving obstacles[J]. Mechanical Systems and Signal Processing, 2018, 100: 482-500.
增加
[52] Likhachev M, Ferguson D. Planning long dynamically feasible maneuvers for autonomous vehicles[J]. The International Journal of Robotics Research, 2009, 28(8): 933-945.
小鄔：學習運動規劃該看什麼書
小鄔：運動規劃綜述文章
推薦閱讀：
