机器人运动规划方法综述

doi:10.7527/S1000-6893.2021.26495

Abstract

Abstract:

As application scenarios become more complex， the need for autonomous motion planning techniques which aims at generating collision-free path （trajectory） becomes more urgent. Although a large number of planning algorithms adapted to different scenarios have been proposed already， how to properly classify the existing results and analyze the advantages and disadvantages of different methods is still a problem that needs in-depth consideration. In this paper， the basic connotation of motion planning and the key steps of classical algorithms are explained. Secondly， aiming at the contradiction between real-time performance and the quality of solution path （trajectory）， the existing algorithm acceleration strategies are analyzed and summarized hierarchically based on whether differential constraint is considered. Finally， facing the new requirements of planning under uncertainty （i.e.， sensor uncertainty， future state uncertainty and environmental uncertainty） and intelligent planning， the latest achievements and development direction in the field of motion planning are reviewed. It is expected that the review can provide ideas for future research.

Key words: robot, combined motion planning, sample-based motion planning, optimized-based motion planning, feedback motion planning

CLC Number:

V249.121

Yongxing TANG, Zhanxia ZHU, Hongwen ZHANG, Jianjun LUO, Jianping YUAN. A tutorial and review on robot motion planning[J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2023, 44(2): 26495-026495.

Figures/Tables 20

Fig.1

Fig.2

Table 1

Fig.3

Fig.4

Fig.5

Fig.6

Fig.7

Fig.8

Fig.9

Fig.10

Table 2

Summary of acceleration strategies or solution quality improvement strategies for SBMP

问题类型	可用信息	技术描述	相关文献
传统运动规划	确定性采样点集或序列	用确定性采样过程代替随机采样，保障算法的确定性渐进最优性或分辨率完备性，改善收敛率、计算复杂度和时间复杂度	［88］，［91］，［93］
	C_free形状信息	根据推测得到的C_free形状，增加与可行路径解相关的困难区域的采样点数量	［95］~［102］，［103］~［108］
	解路径代价或尚需代价的估值	用已有的解路径代价限制SBMP的搜索区域，达到加速算法的目的	［14］，［110］，［112］~［114］，［116］
	解路径代价或尚需代价的估值	用尚需代价的估值安排搜索次序，克服早期SBMP算法盲目搜索的缺点	［15］~［17］，［119］~［121］
	之前有效的搜索信息或由传感器获得的动态障碍物运动信息	从目标构型反向搜索；遭遇障碍物后，保留之前的部分有效信息，并在此基础上增强采样树（路图），以减少重规划的时间	［125］，［126］，［128］~［130］
	之前有效的搜索信息或由传感器获得的动态障碍物运动信息	预测动态障碍物的行为或轨迹，以提高解品质，降低重规划频次	［131］，［132］
	编码C-space信息、最优路径信息的训练数据集	用数据集训练CAE，CVAE，CNN，GNN等，以为SBMP提供采样点或直接生成可行（近优）路径	［18］，［19］，［136］，［138］~［143］
	在与环境交互中学习到的信息	将强化学习与SBMP结合	［145］，［146］，［148］，［150］
考虑微分约束的开环运动规划	状态的可达性信息、状态扩展后的碰撞概率、离散动作集中已使用过的动作信息、采样树对搜索空间的覆盖信息等	在使用较差的度量函数的情况下，利用这些信息引导采样树生长，使其能较快地对初始状态的无碰可达集实现稠密覆盖	［157］，［161］~［169］
	解轨迹的代价信息、近似可达集信息、启发式信息	类似于在传统运动规划算法中的做法，拒绝潜在解轨迹代价大于已有解轨迹代价的采样点；或直接在近似可达集中采样；安排算法的搜索次序	［180］，［182］~［185］，［187］，［188］
	包含大量运动规划问题解信息的训练集	1）端到端地生成轨迹；2）学习在无碰可达集内生成稠密（最优）的采样点分布；3）在不考虑障碍物的情况下，学习针对复杂系统的LPM；4）学习有关NSM的度量函数	［23］~［28］，［170］~［173］，［191］，［192］

Table 2

Fig.11

Fig.12

Table 3

Summary of optimal algorithms considering differential constraints［78］

	收敛性质	结构	算法	条件
传统运动规划	几乎一定	路图	PRM*	$r n > 2 1 + 1 d 1 d μ C f r e e ξ d 1 d l o g n n 1 d$ $k n > e 1 + 1 d l o g n$
	概率性	路图上的搜索树	FMT*	$r n > 2 1 d 1 d μ C f r e e ξ d 1 d l o g n n 1 d$
	概率性	带有Rewiring的树	RRT*	$r n ≥ 2 + θ 1 + φ 4 c * d + 1 θ 1 - ψ 1 d + 1 μ C f r e e ξ d 1 d + 1 l o g n n 1 d + 1$
	确定性，基于离散度	路图	PRM* FMT*	如果采样离散度为 $O 1 n 1 d$ ，则 $r n ∈ ω 1 n 1 d$
含微分约束的运动规划	概率性	前向搜索树	SST*	随机选择；蒙特卡洛传播：随机控制和随机积分时间
	概率性	前向搜索树	AO-RRT	在增强的State-Cost空间中用RRT选择；蒙特卡洛传播
	概率性	Meta算法	AO-X	重复调用有一个有递减代价界的概率完备算法X
			CHOMP，STOMP	用确定性协变方法或概率梯度下降方法求解无约束优化问题
	部分算法提供了收敛性保证		TrajOpt，SCvx，GuSTO	建立恰当的障碍物约束；非凸问题的凸化
			凸分解方法	SFC的快速生成；时间分配；区间分配

Table 3

Fig.13

Fig.14

Fig.15

Table 4

Table 5

Summary of advantages and disadvantages of various motion planning algorithms

运动规划问题的类型	算法类别	优势	劣势
传统运动规划	CMP	算法具有完备性	不适用于高维运动规划问题和障碍物数量巨大的问题
传统运动规划	SBMP	1）现实中大多数C-space都具有良好的可视特性是SBMP在较高维空间取得成功的基础，其主要优势在于用可数点集或序列及它们间的连接关系近似C-space的连通特性；2）对于基于采样的路图算法，利用启发式的A*及其变体可以减少计算时间	1）原始SBMP算法的搜索过程是无序的，这在某种程度上将问题的成功求解寄托于概率；2）随机性无法克服维数诅咒；3）原始算法的搜索范围被限定为整个C-space，浪费了大量计算时间；4）算法只能保证概率完备性和分辨率完备性；5）规划结果需要后处理
考虑微分约束的开环运动规划	递增搜索与采样算法	1）得益于自身的碰撞检测模块，避免了显式处理相空间中的障碍物约束；2）可直接得到服从系统运动特性的轨迹；3）具有全局搜索特性	1）度量函数敏感性、随机搜索和搜索范围固定的特点使此类算法的实时性受到严重限制；2）求解复杂系统TPBVP问题的困难性导致此类算法的最优性条件无法满足
考虑微分约束的开环运动规划	基于优化的运动规划算法	1）可直接得到服从系统运动特性的轨迹；2）可借助优化领域大量的成熟工具进行求解；3）部分算法可以用于实时任务	1）对初始猜想敏感；2）算法的收敛特性很难得到保障；3）一般只能得到局部最优解；4）需显式处理障碍物约束；5）非凸问题的凸化较为困难
反馈运动规划	不确定性的显式建模方法	相比隐式建模方法，规划结果的保守性较低	对建模的可靠性要求很强，而显式建立这样的模型往往非常复杂并具有挑战性，故很容易产生建模误差
反馈运动规划	不确定性的隐式建模方法	可在所考虑的不确定性范围内保证机器人运动的绝对安全	1）相比显式建模方法，规划结果有较强的保守性；2）辅助控制器的计算过程较为耗时，需离线进行

Table 5

References 255

1	FARLEY K A， WILLIFORD K H， STACK K M， et al. Mars 2020 mission overview［J］. Space Science Reviews， 2020， 216（8）： 1-41.
2	FLORES-ABAD A， MA O， PHAM K， et al. A review of space robotics technologies for on-orbit servicing［J］. Progress in Aerospace Sciences， 2014， 68（8）： 1-26.
3	ROOT P. Fast lightweight autonomy［EB/OL］. （2018-12-13）［2021-11-27］. .
4	BUEHLER M， IAGNEMMA K， SINGH S AND， et al. The DARPA Urban Challenge： autonomous vehicles in city traffic［M］. Berlin： Springer， 2009.
5	JANAI J， GÜNEY F， BEHL A， et al. Computer vision for autonomous vehicles： problems， datasets and state of the art［J］. Foundations and Trends® in Computer Graphics and Vision， 2020， 12（1-3）： 1-308.
6	KOCHENDERFER M J. Decision making under uncertainty［M］. Cambridge： The MIT Press， 2015.
7	SCHWARTING W， ALONSO-MORA J， RUS D. Planning and decision-making for autonomous vehicles［J］. Annual Review of Control， Robotics， and Autonomous Systems， 2018， 1（1）： 187-210.
8	LAVALLE S M. Planning algorithms［M］. Cambridge： Cambridge University Press， 2006.
9	CHOSET H M， LYNCH K M， HUTCHINSON S， et al. Principles of robot motion［M］. Cambridge： The MIT Press， 2005.
10	LATOMBE J C. Robot motion planning［M］. Boston： Springer， 1991.
11	FRANKLIN G F， POWELL J D， EMAMI-NAEINI A. Feedback control of dynamic systems［M］. London： Pearson， 2018.
12	LOZANO-PEREZ T. Spatial planning： a configuration space approach［M］∥Autonomous robot vehicles. New York： Springer， 1990： 259-271.
13	RUSSELL S， NORVIG P. Artificial intelligence： a modern approach［M］. Upper Saddle River： Prentice Hall， 2010.
14	GAMMELL J D， SRINIVASA S S， BARFOOT T D. Informed RRT*： optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic［C］∥2014 IEEE/RSJ International Conference on Intelligent Robots and Systems. Piscataway： IEEE Press， 2014： 2997-3004.
15	JANSON L， SCHMERLING E， CLARK A， et al. Fast marching tree： a fast marching sampling-based method for optimal motion planning in many dimensions［J］. The International Journal of Robotics Research， 2015， 34（7）： 883-921.
16	GAMMELL J D， SRINIVASA S S， BARFOOT T D. Batch Informed Trees （BIT*）： sampling-based optimal planning via the heuristically guided search of implicit random geometric graphs［C］∥2015 IEEE International Conference on Robotics and Automation （ICRA）. Piscataway： IEEE Press， 2015： 3067-3074.
17	GAMMELL J D， BARFOOT T D， SRINIVASA S S. Batch Informed Trees （BIT*）： informed asymptotically optimal anytime search［J］. The International Journal of Robotics Research， 2020， 39（5）： 543-567.
18	ICHTER B， HARRISON J， PAVONE M. Learning sampling distributions for robot motion planning［C］∥2018 IEEE International Conference on Robotics and Automation （ICRA）. Piscataway： IEEE Press， 2018： 7087-7094.
19	QURESHI A H， MIAO Y L， SIMEONOV A， et al. Motion planning networks： bridging the gap between learning-based and classical motion planners［J］. IEEE Transactions on Robotics， 2021， 37（1）： 48-66.
20	HAUSER K， ZHOU Y L. Asymptotically optimal planning by feasible kinodynamic planning in a state-cost space［J］. IEEE Transactions on Robotics， 2016， 32（6）： 1431-1443.
21	KLEINBORT M， GRANADOS E， SOLOVEY K， et al. Refined analysis of asymptotically-optimal kinodynamic planning in the state-cost space［C］∥2020 IEEE International Conference on Robotics and Automation （ICRA）. Piscataway： IEEE Press， 2020： 6344-6350.
22	LI Y B， LITTLEFIELD Z， BEKRIS K E. Asymptotically optimal sampling-based kinodynamic planning［J］. The International Journal of Robotics Research， 2016， 35（5）： 528-564.
23	LI L J， MIAO Y L， QURESHI A H， et al. MPC-MPNet： model-predictive motion planning networks for fast， near-optimal planning under kinodynamic constraints［J］. IEEE Robotics and Automation Letters， 2021， 6（3）： 4496-4503.
24	FRANCIS A， FAUST A， CHIANG H T L， et al. Long-range indoor navigation with PRM-RL［J］. IEEE Transactions on Robotics， 2020， 36（4）： 1115-1134.
25	FAUST A， OSLUND K， RAMIREZ O， et al. PRM-RL： long-range robotic navigation tasks by combining reinforcement learning and sampling-based planning［C］∥2018 IEEE International Conference on Robotics and Automation （ICRA）. Piscataway： IEEE Press， 2018： 5113-5120.
26	CHIANG H T L， HSU J， FISER M， et al. RL-RRT： kinodynamic motion planning via learning reachability estimators from RL policies［J］. IEEE Robotics and Automation Letters， 2019， 4（4）： 4298-4305.
27	ICHTER B， PAVONE M. Robot motion planning in learned latent spaces［J］. IEEE Robotics and Automation Letters， 2019， 4（3）： 2407-2414.
28	QURESHI A H， DONG J G， CHOE A， et al. Neural manipulation planning on constraint manifolds［J］. IEEE Robotics and Automation Letters， 2020， 5（4）： 6089-6096.
29	RATLIFF N， ZUCKER M， BAGNELL J A， et al. CHOMP： gradient optimization techniques for efficient motion planning［C］∥2009 IEEE International Conference on Robotics and Automation. Piscataway： IEEE Press， 2009： 489-494.
30	ZUCKER M， RATLIFF N， DRAGAN A D， et al. CHOMP： Covariant Hamiltonian optimization for motion planning［J］. The International Journal of Robotics Research， 2013， 32（9-10）： 1164-1193.
31	KALAKRISHNAN M， CHITTA S， THEODOROU E， et al. STOMP： stochastic trajectory optimization for motion planning［C］∥2011 IEEE International Conference on Robotics and Automation. Piscataway： IEEE Press， 2011： 4569-4574.
32	SCHULMAN J， HO J， LEE A X， et al. Finding locally optimal， collision-free trajectories with sequential convex optimization［C］∥Robotics： Science and Systems IX， 2013： 1-10.
33	SCHULMAN J， DUAN Y， HO J， et al. Motion planning with sequential convex optimization and convex collision checking［J］. The International Journal of Robotics Research， 2014， 33（9）： 1251-1270.
34	MAO Y Q， SZMUK M， AÇIKMEŞE B. Successive convexification of non-convex optimal control problems and its convergence properties［C］∥2016 IEEE 55th Conference on Decision and Control （CDC）. Piscataway： IEEE Press， 2016： 3636-3641.
35	MAO Y Q， SZMUK M， XU X R， et al. Successive convexification： a superlinearly convergent algorithm for non-convex optimal control problems［DB/OL］. arXiv preprint arXiv： 1804.06539v2， 2019.
36	BONALLI R， CAULIGI A， BYLARD A， et al. GuSTO： guaranteed sequential trajectory optimization via sequential convex programming［C］∥2019 International Conference on Robotics and Automation （ICRA）. Piscataway： IEEE Press， 2019： 6741-6747.
37	LIU S K， WATTERSON M， MOHTA K， et al. Planning dynamically feasible trajectories for quadrotors using safe flight corridors in 3-D complex environments［J］. IEEE Robotics and Automation Letters， 2017， 2（3）： 1688-1695.
38	CHEN J， LIU T B， SHEN S J. Online generation of collision-free trajectories for quadrotor flight in unknown cluttered environments［C］∥2016 IEEE International Conference on Robotics and Automation （ICRA）. Piscataway： IEEE Press， 2016： 1476-1483.
39	GAO F， WU W， GAO W L， et al. Flying on point clouds： Online trajectory generation and autonomous navigation for quadrotors in cluttered environments［J］. Journal of Field Robotics， 2019， 36（4）： 710-733.
40	SILVER D， VENESS J. Monte-Carlo planning in large POMDPs［C］∥Proceedings of the 23rd International Conference on Neural Information Processing Systems， 2010： 2164-2172.
41	YE N， SOMANI A， HSU D， et al. DESPOT： online POMDP planning with regularization［J］. Journal of Artificial Intelligence Research， 2017， 58： 231-266.
42	SUNBERG Z N， KOCHENDERFER M J. Online algorithms for POMDPs with continuous state， action， and observation spaces［C］∥Twenty-Eighth International Conference on Automated Planning and Scheduling， 2018： 259-263.
43	PRIYADARSHINI GARG N， HSU D， SUN LEE W. DESPOT-alpha： online POMDP planning with large state and observation spaces［C］∥Robotics： Science and Systems XV， 2019： 49-58.
44	CHEN M， HERBERT S， HU H M， et al. FaSTrack： a modular framework for real-time motion planning and guaranteed safe tracking［DB/OL］. arXiv preprint： 2102.07039，2012.
45	MAJUMDAR A， TEDRAKE R. Funnel libraries for real-time robust feedback motion planning［J］. The International Journal of Robotics Research， 2017， 36（8）： 947-982.
46	AMES A D， XU X R， GRIZZLE J W， et al. Control barrier function based quadratic programs for safety critical systems［J］. IEEE Transactions on Automatic Control， 2017， 62（8）： 3861-3876.
47	AMES A D， COOGAN S， EGERSTEDT M， et al. Control barrier functions： theory and applications［C］∥2019 18th European Control Conference （ECC）. Piscataway： IEEE Press， 2019： 3420-3431.
48	SINGH S， MAJUMDAR A， SLOTINE J J， et al. Robust online motion planning via contraction theory and convex optimization［C］∥2017 IEEE International Conference on Robotics and Automation （ICRA）. Piscataway： IEEE Press， 2017： 5883-5890.
49	GONZÁLEZ D， PÉREZ J， MILANÉS V， et al. A review of motion planning techniques for automated vehicles［J］. IEEE Transactions on Intelligent Transportation Systems， 2016， 17（4）： 1135-1145.
50	PADEN B， ČÁP M， YONG S Z， et al. A survey of motion planning and control techniques for self-driving urban vehicles［J］. IEEE Transactions on Intelligent Vehicles， 2016， 1（1）： 33-55.
51	ELBANHAWI M， SIMIC M. Sampling-based robot motion planning： a review［J］. IEEE Access， 2014， 2： 56-77.
52	CHAZELLE B. Approximation and decomposition of shapes［M］∥Algorithmic and geometric aspects of robotics. New York： Routledge， 2016： 161-202.
53	SCHWARTZ J T， SHARIR M. On the “piano movers” problem. II. General techniques for computing topological properties of real algebraic manifolds［J］. Advances in Applied Mathematics， 1983， 4（3）： 298-351.
54	NILSSON N J. A mobile automaton： an application of artificial intelligence techniques［R］. 1969.
55	Ó'DÚNLAING C， SHARIR M， YAP C K. Retraction： a new approach to motion-planning［C］∥Proceedings of the fifteenth annual ACM symposium on Theory of computing. New York： ACM Press， 1983： 207-220.
56	CANNY J. The complexity of robot motion planning［M］. Cambridge： The MIT press， 1988.
57	DIJKSTRA E W. A note on two problems in connexion with graphs［J］. Numerische Mathematik， 1959， 1（1）： 269-271.
58	HART P E， NILSSON N J， RAPHAEL B. A formal basis for the heuristic determination of minimum cost paths［J］. IEEE Transactions on Systems Science and Cybernetics， 1968， 4（2）： 100-107.
59	LIKHACHEV M， GORDON G J， THRUN S. ARA： anytime A with provable bounds on sub-optimality［C］ ∥Proceedings of 2003 Advances in Neural Information Processing Systems. Cambridge： The MIT Press， 2003： 767-774.
60	KOENIG S， LIKHACHEV M. D*lite［C］∥Proceedings of the Eighteenth National Conference on Artificial Intelligence. Menlo Park： AAAI Press， 2002： 476-483.
61	LIKHACHEV M， FERGUSON D I， GORDON G J， et al. Anytime dynamic A*： An anytime， replanning algorithm［C］∥Proceedings of the Fifteenth International Conference on International Conference on Automated Planning and Scheduling. Menlo Park： AAAI Press， 2005： 262-271.
62	DANIEL K， NASH A， KOENIG S， et al. Theta*： any-angle path planning on grids［J］. Journal of Artificial Intelligence Research， 2010， 39： 533-579.
63	NASH A， KOENIG S， TOVEY C. Lazy theta*： any-angle path planning and path length analysis in 3D［C］∥ Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence. Menlo Park： AAAI Press， 2010： 147-154.
64	LINDEMANN S R， LAVALLE S M. Current issues in sampling-based motion planning［C］∥The Eleventh International Symposium on Robotics Research. Berlin： Springer， 2005： 36-54.
65	KAVRAKI L E， SVESTKA P， LATOMBE J C， et al. Probabilistic roadmaps for path planning in high-dimensional configuration spaces［J］. IEEE Transactions on Robotics and Automation， 1996， 12（4）： 566-580.
66	KAVRAKI L E， KOLOUNTZAKIS M N， LATOMBE J C. Analysis of probabilistic roadmaps for path planning［J］. IEEE Transactions on Robotics and Automation， 1998， 14（1）： 166-171.
67	HSU D， LATOMBE J C， MOTWANI R. Path planning in expansive configuration spaces［C］∥Proceedings of International Conference on Robotics and Automation. Piscataway： IEEE Press， 1997： 2719-2726.
68	BARRAQUAND J， KAVRAKI L， LATOMBE J C， et al. A random sampling scheme for path planning［J］. The International Journal of Robotics Research， 1997， 16（6）： 759-774.
69	CHAUDHURI S， KOLTUN V. Smoothed analysis of probabilistic roadmaps［J］. Computational Geometry， 2009， 42（8）： 731-747.
70	LAVALLE S M. Rapidly-exploring random trees： a new tool for path planning： TR 98-11［R］. 1998.
71	LAVALLE S M， KUFFNER J J J. Randomized kinodynamic planning［J］. The International Journal of Robotics Research， 2001， 20（5）： 378-400.
72	LAVALLE S M， KUFFNER J J J， DONALD B R. Rapidly-exploring random trees： progress and prospects［M］∥Algorithmic and computational robotics. 2001： 303-307.
73	KUFFNER J J J， LAVALLE S M. RRT-connect： an efficient approach to single-query path planning［C］∥IEEE International Conference on Robotics and Automation Symposia Proceedings. Piscataway： IEEE Press， 2000： 995-1001.
74	BOHLIN R， KAVRAKI L E. Path planning using lazy PRM［C］∥IEEE International Conference on Robotics and Automation Symposia Proceedings. Piscataway： IEEE Press， 2000： 521-528.
75	SÁNCHEZ G， LATOMBE J C. On delaying collision checking in PRM planning： application to multi-robot coordination［J］. The International Journal of Robotics Research， 2002， 21（1）： 5-26.
76	GERAERTS R， OVERMARS M H. Creating high-quality paths for motion planning［J］. The International Journal of Robotics Research， 2007， 26（8）： 845-863.
77	KARAMAN S， FRAZZOLI E. Sampling-based algorithms for optimal motion planning［J］. The International Journal of Robotics Research， 2011， 30（7）： 846-894.
78	BEKRIS K E， SHOME R. Asymptotically optimal sampling-based planners［DB/OL］. arXiv preprint arXiv：， 2019.
79	SOLOVEY K， SALZMAN O， HALPERIN D. New perspective on sampling-based motion planning via random geometric graphs［J］. The International Journal of Robotics Research， 2018， 37（10）： 1117-1133.
80	SOLOVEY K， KLEINBORT M. The critical radius in sampling-based motion planning［J］. The International Journal of Robotics Research， 2020， 39（2-3）： 266-285.
81	SOLOVEY K， JANSON L， SCHMERLING E， et al. Revisiting the asymptotic optimality of RRT［C］∥2020 IEEE International Conference on Robotics and Automation （ICRA）. Piscataway： IEEE Press， 2020： 2189-2195.
82	YERSHOVA A， LAVALLE S M. Improving motion-planning algorithms by efficient nearest-neighbor searching［J］. IEEE Transactions on Robotics， 2007， 23（1）： 151-157.
83	KUFFNER J J JR. Effective sampling and distance metrics for 3D rigid body path planning［C］∥2004 IEEE International Conference on Robotics and Automation. Piscataway： IEEE Press， 2004： 3993-3998.
84	AMATO N M， BAYAZIT O B， DALE L K， et al. Choosing good distance metrics and local planners for probabilistic roadmap methods［J］. IEEE Transactions on Robotics and Automation， 2000， 16（4）： 442-447.
85	PLAKU E， BEKRIS K E， CHEN B Y， et al. Sampling-based roadmap of trees for parallel motion planning［J］. IEEE Transactions on Robotics， 2005， 21（4）： 597-608.
86	GERAERTS R， OVERMARS M H. A comparative study of probabilistic roadmap planners［M］∥Algorithmic foundations of robotics V. Berlin： Springer， 2004： 43-57.
87	TOTH C D， O'ROURKE J， GOODMAN J E， et al. Handbook of discrete and computational geometry［M］. 2017.
88	LAVALLE S M， BRANICKY M S， LINDEMANN S R. On the relationship between classical grid search and probabilistic roadmaps［J］. The International Journal of Robotics Research， 2004， 23（7-8）： 673-692.
89	BRANICKY M S， LAVALLE S M， OLSON K， et al. Quasi-randomized path planning［C］∥ 2001 IEEE International Conference on Robotics and Automation. Piscataway： IEEE Press， 2001： 1481-1487.
90	SUKHAREV A G. Optimal strategies of the search for an extremum［J］. USSR Computational Mathematics and Mathematical Physics， 1971， 11（4）： 119-137.
91	JANSON L， ICHTER B， PAVONE M. Deterministic sampling-based motion planning： optimality， complexity， and performance［J］. The International Journal of Robotics Research， 2018， 37（1）： 46-61.
92	NIEDERREITER H. Random number generation and quasi-Monte Carlo methods［M］. Philadelphia： Society for Industrial and Applied Mathematics， 1992.
93	PALMIERI L， BRUNS L， MEURER M， et al. Dispertio： optimal sampling for safe deterministic motion planning［J］. IEEE Robotics and Automation Letters， 2020， 5（2）： 362-368.
94	HSU D， LATOMBE J C， KURNIAWATI H. On the probabilistic foundations of probabilistic roadmap planning［J］. The International Journal of Robotics Research， 2006， 25（7）： 627-643.
95	VAN DEN BERG J P， OVERMARS M H. Using workspace information as a guide to non-uniform sampling in probabilistic roadmap planners［J］. The International Journal of Robotics Research， 2005， 24（12）： 1055-1071.
96	HOLLEMAN C， KAVRAKI L E. A framework for using the workspace medial axis in PRM planners［C］∥2000 IEEE International Conference on Robotics and Automation Symposia Proceedings. Piscataway： IEEE Press， 2000： 1408-1413.
97	YANG Y D， BROCK O. Adapting the sampling distribution in PRM planners based on an approximated medial axis［C］∥2004 IEEE International Conference on Robotics and Automation. Piscataway： IEEE Press， 2004： 4405-4410.
98	FOSKEY M， GARBER M， LIN M C， et al. A Voronoi-based hybrid motion planner［C］∥ 2001 IEEE/RSJ International Conference on Intelligent Robots and Systems. Piscataway： IEEE Press， 2001： 55-60.
99	AMATO N M， BAYAZIT O B， DALE L K， et al. OBPRM： An obstacle-based PRM for 3D workspaces［M］∥Robotics： The Algorithmic Perspective. 1998： 165-178.
100	BOOR V， OVERMARS M H， VAN DER STAPPEN A F. The Gaussian sampling strategy for probabilistic roadmap planners［C］∥1999 IEEE International Conference on Robotics and Automation. Piscataway： IEEE Press， 1999： 1018-1023.
101	SIMÉON T， LAUMOND J P， NISSOUX C. Visibility-based probabilistic roadmaps for motion planning［J］. Advanced Robotics， 2000， 14（6）： 477-493.
102	HSU D， JIANG T T， REIF J， et al. The bridge test for sampling narrow passages with probabilistic roadmap planners［C］∥2003 IEEE International Conference on Robotics and Automation. Piscataway： IEEE Press， 2003： 4420-4426.
103	HSU D， SANCHEZ-ANTE G， SUN Z. Hybrid PRM sampling with a cost-sensitive adaptive strategy［C］∥ 2005 IEEE International Conference on Robotics and Automation. Piscataway： IEEE Press， 2005： 3874-3880.
104	YERSHOVA A， JAILLET L， SIMEON T， et al. Dynamic-domain RRTs： efficient exploration by controlling the sampling domain［C］∥2005 IEEE International Conference on Robotics and Automation. Piscataway： IEEE Press， 2005： 3856-3861.
105	JAILLET L， YERSHOVA A， LA VALLE S M， et al. Adaptive tuning of the sampling domain for dynamic-domain RRTs［C］∥2005 IEEE/RSJ International Conference on Intelligent Robots and Systems. Piscataway： IEEE Press， 2005： 2851-2856.
106	BURNS B， BROCK O. Sampling-based motion planning using predictive models［C］∥2005 IEEE International Conference on Robotics and Automation. Piscataway： IEEE Press， 2005： 3120-3125.
107	BURNS B， BROCK O. Toward optimal configuration space sampling［C］∥Robotics： Science and Systems I， 2005： 105-112.
108	BURNS B， BROCK O. Single-query motion planning with utility-guided random trees［C］∥2007 IEEE International Conference on Robotics and Automation. Piscataway： IEEE Press， 2007： 3307-3312.
109	URMSON C， SIMMONS R. Approaches for heuristically biasing RRT growth［C］∥2003 IEEE/RSJ International Conference on Intelligent Robots and Systems. Piscataway： IEEE Press， 2003： 1178-1183.
110	FERGUSON D， STENTZ A. Anytime RRTs［C］∥2006 IEEE/RSJ International Conference on Intelligent Robots and Systems. Piscataway： IEEE Press， 2006： 5369-5375.
111	JAILLET L， CORTÉS J， SIMÉON T. Sampling-based path planning on configuration-space costmaps［J］. IEEE Transactions on Robotics， 2010， 26（4）： 635-646.
112	KARAMAN S， WALTER M R， PEREZ A， et al. Anytime motion planning using the RRT［C］∥2011 IEEE International Conference on Robotics and Automation. Piscataway： IEEE Press， 2011： 1478-1483.
113	HAUSER K. Lazy collision checking in asymptotically-optimal motion planning［C］∥2015 IEEE International Conference on Robotics and Automation （ICRA）. Piscataway： IEEE Press， 2015： 2951-2957.
114	AKGUN B， STILMAN M. Sampling heuristics for optimal motion planning in high dimensions［C］∥2011 IEEE/RSJ International Conference on Intelligent Robots and Systems. Piscataway： IEEE Press， 2011： 2640-2645.
115	ISLAM F， NASIR J， MALIK U， et al. RRT*-Smart： rapid convergence implementation of RRT towards optimal solution［C］∥2012 IEEE International Conference on Mechatronics and Automation. Piscataway： IEEE Press， 2012： 1651-1656.
116	ARSLAN O， TSIOTRAS P. Use of relaxation methods in sampling-based algorithms for optimal motion planning［C］∥2013 IEEE International Conference on Robotics and Automation. Piscataway： IEEE Press， 2013： 2421-2428.
117	KOENIG S， LIKHACHEV M， FURCY D. Lifelong planning A* ［J］. Artificial Intelligence， 2004， 155（1-2）： 93-146.
118	GAMMELL J D， BARFOOT T D， SRINIVASA S S. Informed sampling for asymptotically optimal path planning［J］. IEEE Transactions on Robotics， 2018， 34（4）： 966-984.
119	STRUB M P， GAMMELL J D. Advanced BIT（ABIT）： sampling-based planning with advanced graph-search techniques［C］∥2020 IEEE International Conference on Robotics and Automation （ICRA）. Piscataway： IEEE Press， 2020： 130-136.
120	STRUB M P， GAMMELL J D. Adaptively informed trees （AIT*）： fast asymptotically optimal path planning through adaptive heuristics［C］∥2020 IEEE International Conference on Robotics and Automation （ICRA）. Piscataway： IEEE Press， 2020： 3191-3198.
121	CHOUDHURY S， GAMMELL J D， BARFOOT T D， et al. Regionally accelerated batch informed trees （RABIT*）： a framework to integrate local information into optimal path planning［C］∥2016 IEEE International Conference on Robotics and Automation （ICRA）. Piscataway： IEEE Press， 2016： 4207-4214.
122	MARBLE J D， BEKRIS K E. Asymptotically near-optimal planning with probabilistic roadmap spanners［J］. IEEE Transactions on Robotics， 2013， 29（2）： 432-444.
123	DOBSON A， BEKRIS K E. Sparse roadmap spanners for asymptotically near-optimal motion planning［J］. The International Journal of Robotics Research， 2014， 33（1）： 18-47.
124	SALZMAN O， HALPERIN D. Asymptotically near-optimal RRT for fast， high-quality motion planning［J］. IEEE Transactions on Robotics， 2016， 32（3）： 473-483.
125	BRUCE J， VELOSO M M. Real-time randomized path planning for robot navigation［C］∥RoboCup 2002： Robot Soccer World Cup VI. Berlin： Springer， 2003： 288-295.
126	FERGUSON D， KALRA N， STENTZ A. Replanning with RRTs［C］∥2006 IEEE International Conference on Robotics and Automation. Piscataway： IEEE Press， 2006： 1243-1248.
127	STENTZ A. Optimal and efficient path planning for partially known environments［M］∥Intelligent unmanned ground vehicles. Boston： Springer， 1997： 203-220.
128	ZUCKER M， KUFFNER J， BRANICKY M. Multipartite RRTs for rapid replanning in dynamic environments［C］∥2007 IEEE International Conference on Robotics and Automation. Piscataway： IEEE Press， 2007： 1603-1609.
129	VAN DEN BERG J， FERGUSON D， KUFFNER J. Anytime path planning and replanning in dynamic environments［C］∥2006 IEEE International Conference on Robotics and Automation. Piscataway： IEEE Press， 2006： 2366-2371.
130	FERGUSON D， Anytime STENTZ A.， dynamic planning in high-dimensional search spaces［C］∥2007 IEEE International Conference on Robotics and Automation. Piscataway： IEEE Press， 2007： 1310-1315.
131	LEFÈVRE S， VASQUEZ D， LAUGIER C. A survey on motion prediction and risk assessment for intelligent vehicles［J］. Robomech Journal， 2014， 1（1）： 1-14.
132	RUDENKO A， PALMIERI L， HERMAN M， et al. Human motion trajectory prediction： a survey［J］. The International Journal of Robotics Research， 2020， 39（8）： 895-935.
133	RIFAI S， VINCENT P， MULLER X， et al. Contractive auto-encoders： explicit invariance during feature extraction［C］∥28th International Conference on Machine Learning， 2011： 833-840.
134	SOHN K， YAN X C， LEE H. Learning structured output representation using deep conditional generative models［C］∥28th International Conference on Neural Information Processing Systems. Cambridge： The MIT Press， 2015： 3483-3491.
135	WU Z H， PAN S R， CHEN F W， et al. A comprehensive survey on graph neural networks［J］. IEEE Transactions on Neural Networks and Learning Systems， 2021， 32（1）： 4-24.
136	QURESHI A H， YIP M C. Deeply informed neural sampling for robot motion planning［C］∥2018 IEEE/RSJ International Conference on Intelligent Robots and Systems （IROS）. Piscataway： IEEE Press， 2018： 6582-6588.
137	SRIVASTAVA N， HINTON G， KRIZHEVSKY A， et al. Dropout： a simple way to prevent neural networks from overfitting［J］. The Journal of Machine Learning Research， 2014， 15（1）： 1929-1958.
138	WANG J K， CHI W Z， LI C M， et al. Neural RRT*： learning-based optimal path planning［J］. IEEE Transactions on Automation Science and Engineering， 2020， 17（4）： 1748-1758.
139	ICHTER B， SCHMERLING E， LEE T W E， et al. Learned critical probabilistic roadmaps for robotic motion planning［C］∥2020 IEEE International Conference on Robotics and Automation （ICRA）. Piscataway： IEEE Press， 2020： 9535-9541.
140	KUMAR R， MANDALIKA A， CHOUDHURY S， et al. LEGO： leveraging experience in roadmap generation for sampling-based planning［C］∥2019 IEEE/RSJ International Conference on Intelligent Robots and Systems （IROS）. Piscataway： IEEE Press， 2019： 1488-1495.
141	KHAN A， RIBEIRO A， KUMAR V， et al. Graph neural networks for motion planning［DB/OL］. arXiv preprint：2006.06248， 2020.
142	LIU K， STADLER M， ROY N. Learned sampling distributions for efficient planning in hybrid geometric and object-level representations［C］∥2020 IEEE International Conference on Robotics and Automation （ICRA）. Piscataway： IEEE Press， 2020： 9555-9562.
143	QURESHI A H， SIMEONOV A， BENCY M J， et al. Motion planning networks［C］∥2019 International Conference on Robotics and Automation （ICRA）. Piscataway： IEEE Press， 2019： 2118-2124.
144	SUTTON R S， BARTO A G. Reinforcement learning： an introduction［M］. Cambridge： The MIT Press， 2018.
145	HUH J， LEE D D. Efficient sampling with Q-learning to guide rapidly exploring random trees［J］. IEEE Robotics and Automation Letters， 2018， 3（4）： 3868-3875.
146	CHEN B， DAI B， LIN Q， et al. Learning to plan in high dimensions via neural exploration-exploitation trees ［DB/OL］. arXiv preprint：1903.00070， 2019.
147	TAMAR A， WU Y， THOMAS G， et al. Value iteration networks［DB/OL］. arXiv preprint：1602.02867， 2016.
148	BHARDWAJ M， CHOUDHURY S， BOOTS B， et al. Leveraging experience in lazy search［C］∥Robotics： Science and Systems XV， 2019： 464-472.
149	CHOUDHURY S， BHARDWAJ M， ARORA S， et al. Data-driven planning via imitation learning［J］. The International Journal of Robotics Research， 2018， 37（13-14）： 1632-1672.
150	ZHANG C， HUH J， LEE D D. Learning implicit sampling distributions for motion planning［C］∥2018 IEEE/RSJ International Conference on Intelligent Robots and Systems （IROS）. Piscataway： IEEE Press， 2018： 3654-3661.
151	MELLINGER D， KUMAR V. Minimum snap trajectory generation and control for quadrotors［C］∥2011 IEEE International Conference on Robotics and Automation. Piscataway： IEEE Press， 2011： 2520-2525.
152	RICHTER C， BRY A， ROY N. Polynomial trajectory planning for aggressive quadrotor flight in dense indoor environments［M］∥Robotics Research. Cham： Springer， 2016： 649-666.
153	DONALD B， XAVIER P， CANNY J， et al. Kinodynamic motion planning［J］. Journal of the ACM， 1993， 40（5）： 1048-1066.
154	PONTRYAGIN L S. Mathematical theory of optimal processes［M］. London： Routledge， 2018.
155	HSU D， KINDEL R， LATOMBE J C， et al. Randomized kinodynamic motion planning with moving obstacles［J］. The International Journal of Robotics Research， 2002， 21（3）： 233-255.
156	KIM J， ESPOSITO J M， KUMAR V. An RRT-based algorithm for testing and validating multi-robot controllers［C］∥Robotics： Science and Systems I， 2005： 249-256.
157	JAILLET L， HOFFMAN J， VAN DEN BERG J， et al. EG-RRT： Environment-guided random trees for kinodynamic motion planning with uncertainty and obstacles［C］∥2011 IEEE/RSJ International Conference on Intelligent Robots and Systems. Piscataway： IEEE Press， 2011： 2646-2652.
158	FRAZZOLI E， DAHLEH M A， FERON E. Real-time motion planning for agile autonomous vehicles［J］. Journal of Guidance， Control， and Dynamics， 2002， 25（1）： 116-129.
159	LEWIS F L， VRABIE D L， SYRMOS V L. Optimal control［M］. Hoboken： John Wiley & Sons， Inc， 2012.
160	GLASSMAN E， TEDRAKE R. A quadratic regulator-based heuristic for rapidly exploring state space［C］∥2010 IEEE International Conference on Robotics and Automation. Piscataway： IEEE Press， 2010： 5021-5028.
161	CHENG P， LAVALLE S M. Resolution complete rapidly-exploring random trees［C］∥2002 IEEE International Conference on Robotics and Automation. Piscataway： IEEE Press， 2002： 267-272.
162	CHENG P， LAVALLE S M. Reducing metric sensitivity in randomized trajectory design［C］∥2001 IEEE/RSJ International Conference on Intelligent Robots and Systems. Piscataway： IEEE Press， 2001： 43-48.
163	KALISIAK M， VAN DE PANNE M. RRT-blossom： RRT with a local flood-fill behavior［C］∥2006 IEEE International Conference on Robotics and Automation. Piscataway： IEEE Press， 2006： 1237-1242.
164	SHKOLNIK A， WALTER M， TEDRAKE R. Reachability-guided sampling for planning under differential constraints［C］∥2009 IEEE International Conference on Robotics and Automation. Piscataway： IEEE Press， 2009： 2859-2865.
165	LADD A M， KAVRAKI L E. Fast tree-based exploration of state space for robots with dynamics［M］∥Algorithmic Foundations of Robotics VI. Berlin： Springer， 2004： 297-312.
166	LADD A M， KAVRAKI L E. Motion planning in the presence of drift， underactuation and discrete system changes［C］∥Robotics： Science and Systems I， 2005： 233-240.
167	BEKRIS K E， KAVRAKI L E. Greedy but safe replanning under kinodynamic constraints［C］∥2007 IEEE International Conference on Robotics and Automation. Piscataway： IEEE Press， 2007： 704-710.
168	ŞUCAN I A， KAVRAKI L E. Kinodynamic motion planning by interior-exterior cell exploration［M］∥Algorithmic Foundation of Robotics VIII. Berlin： Springer， 2010： 449-464.
169	SUCAN I A， KAVRAKI L E. A sampling-based tree planner for systems with complex dynamics［J］. IEEE Transactions on Robotics， 2012， 28（1）： 116-131.
170	ALLEN R E， PAVONE M. A real-time framework for kinodynamic planning in dynamic environments with application to quadrotor obstacle avoidance［J］. Robotics and Autonomous Systems， 2019， 115： 174-193.
171	BHARATHEESHA M， CAARLS W， WOLFSLAG W J， et al. Distance metric approximation for state-space RRTs using supervised learning［C］∥2014 IEEE/RSJ International Conference on Intelligent Robots and Systems. Piscataway： IEEE Press， 2014： 252-257.
172	PALMIERI L， ARRAS K O. Distance metric learning for RRT-based motion planning with constant-time inference［C］∥2015 IEEE International Conference on Robotics and Automation （ICRA）. Piscataway： IEEE Press， 2015： 637-643.
173	WOLFSLAG W J， BHARATHEESHA M， MOERLAND T M， et al. RRT-CoLearn： towards kinodynamic planning without numerical trajectory optimization［J］. IEEE Robotics and Automation Letters， 2018， 3（3）： 1655-1662.
174	SLOTINE J J E， LI W. Applied nonlinear control［M］. 1991.
175	KARAMAN S， FRAZZOLI E. Optimal kinodynamic motion planning using incremental sampling-based methods［C］∥49th IEEE Conference on Decision and Control （CDC）. Piscataway： IEEE Press， 2010： 7681-7687.
176	OTTE M， FRAZZOLI E. RRTX： Asymptotically optimal single-query sampling-based motion planning with quick replanning［J］. The International Journal of Robotics Research， 2016， 35（7）： 797-822.
177	PEREZ A， PLATT R， KONIDARIS G， et al. LQR-RRT*： optimal sampling-based motion planning with automatically derived extension heuristics［C］∥2012 IEEE International Conference on Robotics and Automation. Piscataway： IEEE Press， 2012： 2537-2542.
178	WEBB D J， VAN DEN BERG J. Kinodynamic RRT*： Asymptotically optimal motion planning for robots with linear dynamics［C］∥2013 IEEE International Conference on Robotics and Automation. Piscataway： IEEE Press， 2013： 5054-5061.
179	GORETKIN G， PEREZ A， PLATT R， et al. Optimal sampling-based planning for linear-quadratic kinodynamic systems［C］∥2013 IEEE International Conference on Robotics and Automation. Piscataway： IEEE Press， 2013： 2429-2436.
180	XIE C， VAN DEN BERG J， PATIL S， et al. Toward asymptotically optimal motion planning for kinodynamic systems using a two-point boundary value problem solver［C］∥2015 IEEE International Conference on Robotics and Automation （ICRA）. Piscataway： IEEE Press， 2015： 4187-4194.
181	NOCEDAL J， WRIGHT S. Numerical optimization［M］. New York： Springer， 2006.
182	SCHMERLING E， JANSON L， PAVONE M. Optimal sampling-based motion planning under differential constraints： The drift case with linear affine dynamics［C］∥2015 54th IEEE Conference on Decision and Control （CDC）. Piscataway： IEEE Press， 2015： 2574-2581.
183	KUNZ T， THOMAZ A， CHRISTENSEN H. Hierarchical rejection sampling for informed kinodynamic planning in high-dimensional spaces［C］∥2016 IEEE International Conference on Robotics and Automation （ICRA）. Piscataway： IEEE Press， 2016： 89-96.
184	YI D Q， THAKKER R， GULINO C， et al. Generalizing informed sampling for asymptotically-optimal sampling-based kinodynamic planning via Markov chain Monte Carlo［C］∥2018 IEEE International Conference on Robotics and Automation （ICRA）. Piscataway： IEEE Press， 2018： 7063-7070.
185	JOSHI S S， HUTCHINSON S， TSIOTRAS P. TIE： time-informed exploration for robot motion planning［J］. IEEE Robotics and Automation Letters， 2021， 6（2）： 3585-3591.
186	KURZHANSKIY A A， VARAIYA P. Ellipsoidal toolbox （ET）［C］∥Proceedings of the 45th IEEE Conference on Decision and Control. Piscataway： IEEE Press， 2006： 1498-1503.
187	LITTLEFIELD Z， BEKRIS K E. Efficient and asymptotically optimal kinodynamic motion planning via dominance-informed regions［C］∥2018 IEEE/RSJ International Conference on Intelligent Robots and Systems （IROS）. Piscataway： IEEE Press， 2018： 1-9.
188	LITTLEFIELD Z， BEKRIS K E. Informed asymptotically near-optimal planning for field robots with dynamics［C］∥Field and Service Robotics. Cham： Springer， 2018： 449-463.
189	PIVTORAIKO M， KNEPPER R A， KELLY A. Differentially constrained mobile robot motion planning in state lattices［J］. Journal of Field Robotics， 2009， 26（3）： 308-333.
190	LIKHACHEV M， FERGUSON D. Planning long dynamically feasible maneuvers for autonomous vehicles［J］. The International Journal of Robotics Research， 2009， 28（8）： 933-945.
191	HUH J， XING G， WANG Z Y， et al. Learning to generate cost-to-go functions for efficient motion planning［M］∥Experimental robotics. Cham： Springer， 2021： 555-565.
192	HUH J， LEE D D， ISLER V. Learning Continuous Cost-to-Go Functions for Non-holonomic Systems［DB/OL］. arXiv preprint：2103.11168， 2021.
193	LILLICRAP T P， HUNT J J， PRITZEL A， et al. Continuous control with deep reinforcement learning［DB/OL］. arXiv preprint：1509.02971， 2015.
194	FAUST A， RUYMGAART P， SALMAN M， et al. Continuous action reinforcement learning for control-affine systems with unknown dynamics［J］. IEEE/CAA Journal of Automatica Sinica， 2014， 1（3）： 323-336.
195	BETTS J T. Survey of numerical methods for trajectory optimization［J］. Journal of Guidance， Control， and Dynamics， 1998， 21（2）： 193-207.
196	KELLY M. An introduction to trajectory optimization： how to do your own direct collocation［J］. SIAM Review， 2017， 59（4）： 849-904.
197	MAYNE D Q， RAWLINGS J B， RAO C V， et al. Constrained model predictive control： Stability and optimality［J］. Automatica， 2000， 36（6）： 789-814.
198	MAYNE D Q. Model predictive control： Recent developments and future promise［J］. Automatica， 2014， 50（12）： 2967-2986.
199	KHATIB O. Real-time obstacle avoidance for manipulators and mobile robots［M］∥Autonomous robot vehicles. New York： Springer， 1986： 396-404.
200	GILL P E， MURRAY W， SAUNDERS M A. SNOPT： an SQP algorithm for large-scale constrained optimization［J］. SIAM Review， 2005， 47（1）： 99-131.
201	WÄCHTER A， BIEGLER L T. On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming［J］. Mathematical Programming， 2006， 106（1）： 25-57.
202	BOYD S， VANDENBERGHE L. Convex optimization［M］. Cambridge： Cambridge University Press， 2004.
203	MALYUTA D， REYNOLDS T P， SZMUK M， et al. Convex optimization for trajectory generation［DB/OL］. arXiv preprint：2106.09125， 2021.
204	ZHANG X J， LINIGER A， BORRELLI F. Optimization-based collision avoidance［J］. IEEE Transactions on Control Systems Technology， 2021， 29（3）： 972-983.
205	DEITS R， TEDRAKE R. Efficient mixed-integer planning for UAVs in cluttered environments［C］∥2015 IEEE International Conference on Robotics and Automation （ICRA）. Piscataway： IEEE Press， 2015： 42-49.
206	BLEKHERMAN G， PARRILO P A， THOMAS R R. Semidefinite optimization and convex algebraic geometry［M］. Philadelphia： Society for Industrial and Applied Mathematics， 2012.
207	HARABOR D， GRASTIEN A. Online graph pruning for pathfinding on grid maps［C］∥Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence， 2011： 1114-1119.
208	THRUN S， BURGARD W， FOX D. Probabilistic robotics［M］. Cambridge： The MIT press， 2005.
209	PINEAU J， GORDON G， THRUN S. Point-based value iteration： an anytime algorithm for POMDPs［C］∥Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence， 2003： 1025-1032.
210	SMITH T， SIMMONS R. Point-based POMDP algorithms： improved analysis and implementation［DB/OL］. arXiv preprint：1207.1412， 2012.
211	SPAAN M T J， VLASSIS N. Perseus： randomized point-based value iteration for POMDPs［J］. Journal of Artificial Intelligence Research， 2005， 24： 195-220.
212	KURNIAWATI H， HSU D， LEE W S. SARSOP： efficient point-based POMDP planning by approximating optimally reachable belief spaces［M］∥Robotics： Science and Systems IV， 2009： 65-72.
213	ROSS S， PINEAU J， PAQUET S， et al. Online planning algorithms for POMDPs［J］. Journal of Artificial Intelligence Research， 2008， 32： 663-704.
214	KURNIAWATI H， YADAV V. An online POMDP solver for uncertainty planning in dynamic environment［M］∥Robotics Research. Cham： Springer， 2016： 611-629.
215	BROWNE C B， POWLEY E， WHITEHOUSE D， et al. A survey of Monte Carlo tree search methods［J］. IEEE Transactions on Computational Intelligence and AI in Games， 2012， 4（1）： 1-43.
216	CAI P P， LUO Y F， HSU D， et al. HyP-DESPOT： a hybrid parallel algorithm for online planning under uncertainty［J］. The International Journal of Robotics Research， 2021， 40（2-3）： 558-573.
217	BAI H， HSU D， LEE W S， et al. Monte Carlo value iteration for continuous-state POMDPs［M］∥Algorithmic Foundations of Robotics IX. Berlin： Springer， 2010： 175-191.
218	BAI H Y， HSU D， LEE W S. Integrated perception and planning in the continuous space： a POMDP approach［J］. The International Journal of Robotics Research， 2014， 33（9）： 1288-1302.
219	PORTA J M， VLASSIS N， SPAAN M T J， et al. Point-based value iteration for continuous POMDPs［J］. Journal of Machine Learning Research， 2006， 7： 2329-2367.
220	HOEY J， POUPART P. Solving POMDPs with continuous or large discrete observation spaces［C］∥Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence. Hong Kong： Professional Book Center， 2005： 1332-1338.
221	SEILER K M， KURNIAWATI H， SINGH S P N. An online and approximate solver for POMDPs with continuous action space［C］∥2015 IEEE International Conference on Robotics and Automation （ICRA）. Piscataway： IEEE Press， 2015： 2290-2297.
222	PRENTICE S， ROY N. The belief roadmap： efficient planning in belief space by factoring the covariance［J］. The International Journal of Robotics Research， 2009， 28（11-12）： 1448-1465.
223	BRY A， ROY N. Rapidly-exploring random belief trees for motion planning under uncertainty［C］∥2011 IEEE International Conference on Robotics and Automation. Piscataway： IEEE Press， 2011： 723-730.
224	VAN DEN BERG J， ABBEEL P， GOLDBERG K. LQG-MP： Optimized path planning for robots with motion uncertainty and imperfect state information［J］. The International Journal of Robotics Research， 2011， 30（7）： 895-913.
225	AGHA-MOHAMMADI A A， CHAKRAVORTY S， AMATO N M. FIRM： Sampling-based feedback motion-planning under motion uncertainty and imperfect measurements［J］. The International Journal of Robotics Research， 2014， 33（2）： 268-304.
226	RAWLINGS J B， MAYNE D Q， DIEHL M. Model predictive control： theory， computation， and design［M］. Madison： Nob Hill Publishing， 2017.
227	SCOKAERT P O M， MAYNE D Q. Min-max feedback model predictive control for constrained linear systems［J］. IEEE Transactions on Automatic Control， 1998， 43（8）： 1136-1142.
228	RAKOVIC S V， KERRIGAN E C， KOURAMAS K I， et al. Invariant approximations of the minimal robust positively invariant set［J］. IEEE Transactions on Automatic Control， 2005， 50（3）： 406-410.
229	MAYNE D Q， SERON M M， RAKOVIĆ S V. Robust model predictive control of constrained linear systems with bounded disturbances［J］. Automatica， 2005， 41（2）： 219-224.
230	RAKOVIĆ S V， KOUVARITAKIS B， FINDEISEN R， et al. Homothetic tube model predictive control［J］. Automatica， 2012， 48（8）： 1631-1638.
231	RAKOVIC S V， KOUVARITAKIS B， CANNON M， et al. Parameterized tube model predictive control［J］. IEEE Transactions on Automatic Control， 2012， 57（11）： 2746-2761.
232	RAKOVIĆ S V， LEVINE W S， AÇIKMESE B. Elastic tube model predictive control［C］∥2016 American Control Conference （ACC）. Piscataway： IEEE Press， 2016： 3594-3599.
233	ALTHOFF M， STURSBERG O， BUSS M. Reachability analysis of nonlinear systems with uncertain parameters using conservative linearization［C］∥2008 47th IEEE Conference on Decision and Control. Piscataway： IEEE Press， 2008： 4042-4048.
234	ALTHOFF M， DOLAN J M. Online verification of automated road vehicles using reachability analysis［J］. IEEE Transactions on Robotics， 2014， 30（4）： 903-918.
235	ALTHOFF D， ALTHOFF M， SCHERER S. Online safety verification of trajectories for unmanned flight with offline computed robust invariant sets［C］∥2015 IEEE/RSJ International Conference on Intelligent Robots and Systems （IROS）. Piscataway： IEEE Press， 2015： 3470-3477.
236	MITCHELL I M， BAYEN A M， TOMLIN C J. A time-dependent Hamilton-Jacobi formulation of reachable sets for continuous dynamic games［J］. IEEE Transactions on Automatic Control， 2005， 50（7）： 947-957.
237	OSHER S， FEDKIW R. Level set methods and dynamic implicit surfaces［M］. New York： Springer New York， 2003.
238	HERBERT S L， CHEN M， HAN S， et al. FaSTrack： a modular framework for fast and guaranteed safe motion planning［C］∥2017 IEEE 56th Annual Conference on Decision and Control （CDC）. Piscataway： IEEE Press， 2017： 1517-1522.
239	SINGH S， CHEN M， HERBERT S L， et al. Robust tracking with model mismatch for fast and safe planning： an SOS optimization approach［DB/OL］. arXiv preprint：1808.00649， 2018.
240	BANSAL S， CHEN M， HERBERT S， et al. Hamilton-Jacobi reachability： a brief overview and recent advances［C］∥2017 IEEE 56th Annual Conference on Decision and Control （CDC）. Piscataway： IEEE Press， 2017： 2242-2253.
241	CHEN M， HERBERT S L， VASHISHTHA M S， et al. Decomposition of reachable sets and tubes for a class of nonlinear systems［J］. IEEE Transactions on Automatic Control， 2018， 63（11）： 3675-3688.
242	HERBERT S L， BANSAL S， GHOSH S， et al. Reachability-based safety guarantees using efficient initializations［C］∥2019 IEEE 58th Conference on Decision and Control （CDC）. Piscataway： IEEE Press， 2019： 4810-4816.
243	LEW T， PAVONE M. Sampling-based reachability analysis： A random set theory approach with adversarial sampling［DB/OL］. arXiv preprint：2008.10180， 2020.
244	BANSAL S， TOMLIN C J. DeepReach： a deep learning approach to high-dimensional reachability［C］∥2021 IEEE International Conference on Robotics and Automation （ICRA）. Piscataway： IEEE Press， 2021： 1817-1824.
245	FISAC J F， LUGOVOY N F， RUBIES-ROYO V， et al. Bridging Hamilton-Jacobi safety analysis and reinforcement learning［C］∥2019 International Conference on Robotics and Automation （ICRA）. Piscataway： IEEE Press， 2019： 8550-8556.
246	DARBON J， LANGLOIS G P， MENG T W. Overcoming the curse of dimensionality for some Hamilton-Jacobi partial differential equations via neural network architectures［J］. Research in the Mathematical Sciences， 2020， 7（3）： 1-50.
247	KHALIL H K， GRIZZLE J W. Nonlinear systems［M］. 2002.
248	TEDRAKE R， MANCHESTER I R， TOBENKIN M， et al. LQR-trees： feedback motion planning via sums-of-squares verification［J］. The International Journal of Robotics Research， 2010， 29（8）： 1038-1052.
249	WANG L， AMES A D， EGERSTEDT M. Safety barrier certificates for collisions-free multirobot systems［J］. IEEE Transactions on Robotics， 2017， 33（3）： 661-674.
250	LOHMILLER W， SLOTINE J J E. On contraction analysis for non-linear systems［J］. Automatica， 1998， 34（6）： 683-696.
251	MANCHESTER I R， SLOTINE J J E. Control contraction metrics： convex and intrinsic criteria for nonlinear feedback design［J］. IEEE Transactions on Automatic Control， 2017， 62（6）： 3046-3053.
252	LUO Y F， BAI H Y， HSU D， et al. Importance sampling for online planning under uncertainty［J］. The International Journal of Robotics Research， 2019， 38（2-3）： 162-181.
253	HEWING L， WABERSICH K P， MENNER M， et al. Learning-based model predictive control： toward safe learning in control［J］. Annual Review of Control， Robotics， and Autonomous Systems， 2020， 3（1）： 269-296.
254	FRIDOVICH-KEIL D， BAJCSY A， FISAC J F， et al. Confidence-aware motion prediction for real-time collision avoidance1［J］. The International Journal of Robotics Research， 2020， 39（2-3）： 250-265.
255	GAL Y， GHAHRAMANI Z. Dropout as a Bayesian approximation： Representing model uncertainty in deep learning［C］∥Proceedings of the 33rd International Conference on International Conference on Machine Learning， 2016： 1050-1059.

不确定性建模方式	算法	技术描述	相关文献
显式方法	基于点的方法	离散模型；用信念空间中的采样点集近似表示信念空间，用离线值迭代方式求得在线执行所依赖的动作策略	［209］~［212］
	POMCP，DESPOT	离散模型；将规划和执行规划结果在线交替进行；蒙特卡洛采样技术	［40］，［41］
	POMCPOW，DESPOT-α	采用一种受粒子滤波启发的加权方案，可较好应对具有连续观测空间的真实问题	［42］，［43］
	BRM，RRBT，LQG-MP，FIRM	结合了传统运动规划和随机最优控制；基于高斯噪声假设，存在一定的局限性	［222］~［225］
隐式方法	FaSTrack	利用H可达性分析离线计算并保存最大跟踪误差，并将使用简化模型进行实时规划的路径或轨迹规划器融入其中	［44］，［238］
	Funnel libraries	利用SOS离线计算Funnels，然后通过在线序列组合达到避障的目的	［45］
	基于CBF的算法	将软约束处理为CLF，将硬约束处理为CBF，并在二次规划的框架下进行求解	［46］，［47］
	基于收缩理论的算法	利用SOS离线计算最优CCMs，从而得到尺寸固定、界面最小的不变Tube及与之相关的反馈跟踪控制器	［48］

[1]	HU Yangxiu, ZHAO Changchun, JIA Chenglong, QIAN Zhouyuan, HU Tao. Synchronous path formation control of UAV swarm based on robot operating system (ROS) [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(S1): 726914-726914.
[2]	DONG Song, ZHENG Kan, MENG Dan, LIAO Wenhe, SUN Lianjun. Robotic drilling of large complex components: A review [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(5): 627133-627133.
[3]	LIAO Wenhe, TIAN Wei, LI Bo, LI Pengcheng, ZHANG Wei, LI Yufei. Error compensation technology and its application progress of an industrial robot [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(5): 627142-627142.
[4]	ZHANG Jiabo, LIU Haitao, YUE Yi, YANG Jizhi, YI Maobin, WANG Yunpeng, ROU Lei. Mobile hybrid robot processing technology for large satellites [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(5): 625731-625731.
[5]	WANG Hao, CHEN Genliang. Research progress and perspective of robotic equipment applied in aviation assembly [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(5): 626128-626128.
[6]	TIAN Wei, CHENG Simiao, LI Bo, LIAO Wenhe. An error compensation method of an industrial robot with joint backlash [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(5): 625569-625569.
[7]	LI Yufei, TIAN Wei, LI Bo, ZHANG Nan. Accuracy control method and experiment of robot milling system [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(5): 625815-625815.
[8]	XIA Pengcheng, LUO Jianjun, WANG Mingming, TAN Longyu. Coordinated stabilization control for dual-arm space robot capturing a non-cooperative target [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(2): 325398-325398.
[9]	LIU Chuankai, LI Dongsheng, XIE Jianfeng, LEI Junxiong, YUAN Chunqiang, HE Ximing. Multi-feature fusion based vision locating method for lunar surface sampling teleoperation [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(12): 326296-326296.
[10]	LIAO Wenhe, ZHENG Kan, SUN Lianjun, DONG Song, ZHANG Lei. Review on chatter stability in robotic machining for large complex components [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(1): 26061-026061.
[11]	JIA Qingxuan, DUAN Jiaqi, CHEN Gang. Uncalibrated visual servo of space robots performing on-orbit assembly alignment task [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021, 42(6): 424063-424063.
[12]	CHU Weimeng, YANG Jinzhao, WU Shu'nan, WU Zhigang. LSTM-based on-orbit identification of inertia tensor for space robot system [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021, 42(11): 524615-524615.
[13]	ZHU Dahu, XU Xiaohu, JIANG Cheng, LI Wenlong. Research progress in robotic grinding technology for complex blades [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021, 42(10): 524265-524265.
[14]	HAN Fei, LIU Fucheng, WANG Zhaolong, DU Xuan, LIU Shanshan, LIU Chaozhen. Multiple line-of-sight angles-only relative navigation by multiple collaborative space robots [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021, 42(1): 524174-524174.
[15]	SUN Yanlong, HE Jun, XING Yan. Multi-target coordinated control of wheel-legged Mars rover [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021, 42(1): 524246-524246.

A tutorial and review on robot motion planning

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 20

References 255

Related Articles 15

Recommended Articles

Metrics

Comments