唐永兴1,2, 朱战霞1,2(), 张红文3, 罗建军1,2, 袁建平1,2
收稿日期:
2021-10-09
修回日期:
2021-10-27
接受日期:
2021-11-18
出版日期:
2023-01-25
发布日期:
2021-12-09
通讯作者:
朱战霞
E-mail:zhuzhanxia@nwpu.edu.cn
基金资助:
Yongxing TANG1,2, Zhanxia ZHU1,2(), Hongwen ZHANG3, Jianjun LUO1,2, Jianping YUAN1,2
Received:
2021-10-09
Revised:
2021-10-27
Accepted:
2021-11-18
Online:
2023-01-25
Published:
2021-12-09
Contact:
Zhanxia ZHU
E-mail:zhuzhanxia@nwpu.edu.cn
Supported by:
摘要:
随着应用场景的日益复杂,机器人对旨在生成无碰撞路径(轨迹)的自主运动规划技术的需求也变得更加迫切。虽然目前已产生了大量适应于不同场景的规划算法,但如何妥善地对现有成果进行归类,并分析不同方法间的优劣异同仍是需要深入思考的问题。以此为切入点,首先,阐释运动规划的基本内涵及经典算法的关键步骤;其次,针对实时性与解路径(轨迹)品质间的矛盾,以是否考虑微分约束为标准,有层次地总结了现有的算法加速策略;最后,面向不确定性(即传感器不确定性、未来状态不确定性和环境不确定性)下的规划和智能规划提出的新需求,对运动规划领域的最新成果和发展方向进行了评述,以期为后续研究提供有益的参考。
中图分类号:
唐永兴, 朱战霞, 张红文, 罗建军, 袁建平. 机器人运动规划方法综述[J]. 航空学报, 2023, 44(2): 26495.
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.
表2
SBMP的加速策略或解品质提升策略总结
问题类型 | 可用信息 | 技术描述 | 相关文献 |
---|---|---|---|
传统运动规划 | 确定性采样点集或序列 | 用确定性采样过程代替随机采样,保障算法的确定性渐进最优性或分辨率完备性,改善收敛率、计算复杂度和时间复杂度 | [ |
Cfree形状信息 | 根据推测得到的Cfree形状,增加与可行路径解相关的困难区域的采样点数量 | [ | |
解路径代价或尚需代价的估值 | 用已有的解路径代价限制SBMP的搜索区域,达到加速算法的目的 | [ | |
用尚需代价的估值安排搜索次序,克服早期SBMP算法盲目搜索的缺点 | [ | ||
之前有效的搜索信息或由传感器获得的动态障碍物运动信息 | 从目标构型反向搜索;遭遇障碍物后,保留之前的部分有效信息,并在此基础上增强采样树(路图),以减少重规划的时间 | [ | |
预测动态障碍物的行为或轨迹,以提高解品质,降低重规划频次 | [ | ||
编码C-space信息、最优路径信息的训练数据集 | 用数据集训练CAE,CVAE,CNN,GNN等,以为SBMP提供采样点或直接生成可行(近优)路径 | [ | |
在与环境交互中学习到的信息 | 将强化学习与SBMP结合 | [ | |
考虑微分约束的开环运动规划 | 状态的可达性信息、状态扩展后的碰撞概率、离散动作集中已使用过的动作信息、采样树对搜索空间的覆盖信息等 | 在使用较差的度量函数的情况下,利用这些信息引导采样树生长,使其能较快地对初始状态的无碰可达集实现稠密覆盖 | [ |
解轨迹的代价信息、近似可达集信息、启发式信息 | 类似于在传统运动规划算法中的做法,拒绝潜在解轨迹代价大于已有解轨迹代价的采样点;或直接在近似可达集中采样;安排算法的搜索次序 | [ | |
包含大量运动规划问题解信息的训练集 | 1) 端到端地生成轨迹;2) 学习在无碰可达集内生成稠密(最优)的采样点分布;3) 在不考虑障碍物的情况下,学习针对复杂系统的LPM;4) 学习有关NSM的度量函数 | [ |
表3
考虑微分约束的最优算法总结[78]
收敛性质 | 结构 | 算法 | 条件 | |
---|---|---|---|---|
传统运动规划 | 几乎一定 | 路图 | PRM* | |
概率性 | 路图上的搜索树 | FMT* | ||
概率性 | 带有Rewiring的树 | RRT* | ||
确定性,基于离散度 | 路图 | PRM* FMT* | 如果采样离散度为 | |
含微分约束的运动规划 | 概率性 | 前向搜索树 | SST* | 随机选择;蒙特卡洛传播:随机控制和随机积分时间 |
概率性 | 前向搜索树 | AO-RRT | 在增强的State-Cost空间中用RRT选择;蒙特卡洛传播 | |
概率性 | Meta算法 | AO-X | 重复调用有一个有递减代价界的概率完备算法X | |
CHOMP,STOMP | 用确定性协变方法或概率梯度下降方法求解无约束优化问题 | |||
部分算法提供了收敛性保证 | TrajOpt,SCvx,GuSTO | 建立恰当的障碍物约束;非凸问题的凸化 | ||
凸分解方法 | SFC的快速生成;时间分配;区间分配 |
表4
反馈运动规划算法总结
不确定性建模方式 | 算法 | 技术描述 | 相关文献 |
---|---|---|---|
显式方法 | 基于点的方法 | 离散模型;用信念空间中的采样点集近似表示信念空间,用离线值迭代方式求得在线执行所依赖的动作策略 | [ |
POMCP,DESPOT | 离散模型;将规划和执行规划结果在线交替进行;蒙特卡洛采样技术 | [ | |
POMCPOW,DESPOT-α | 采用一种受粒子滤波启发的加权方案,可较好应对具有连续观测空间的真实问题 | [ | |
BRM,RRBT,LQG-MP,FIRM | 结合了传统运动规划和随机最优控制;基于高斯噪声假设,存在一定的局限性 | [ | |
隐式方法 | FaSTrack | 利用H可达性分析离线计算并保存最大跟踪误差,并将使用简化模型进行实时规划的路径或轨迹规划器融入其中 | [ |
Funnel libraries | 利用SOS离线计算Funnels,然后通过在线序列组合达到避障的目的 | [ | |
基于CBF的算法 | 将软约束处理为CLF,将硬约束处理为CBF,并在二次规划的框架下进行求解 | [ | |
基于收缩理论的算法 | 利用SOS离线计算最优CCMs,从而得到尺寸固定、界面最小的不变Tube及与之相关的反馈跟踪控制器 | [ |
表5
各类运动规划算法的优劣势总结
运动规划问题的类型 | 算法类别 | 优势 | 劣势 |
---|---|---|---|
传统运动规划 | 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)辅助控制器的计算过程较为耗时,需离线进行 |
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. |
[1] | 赵江, 张璇, 池沛, 王英勋. 空地无人集群自调节控制与动态路径规划方法[J]. 航空学报, 2024, 45(16): 329809-329809. |
[2] | 董豪泽, 陈昱达, 刘丹, 李忠奎. 障碍物空间下分布式轨迹规划的死锁破解[J]. 航空学报, 2023, 44(S2): 729771-729771. |
[3] | 张怀捷, 马静雅, 刘浩源, 郭品, 邓慧超, 徐坤, 丁希仑. 视觉与惯性融合的多旋翼飞行机器人室内定位技术[J]. 航空学报, 2023, 44(5): 426964-426964. |
[4] | 程旋, 赵亦希, 尤舒曼. 机器人柔性翻边成形轨迹优化[J]. 航空学报, 2023, 44(4): 426886-426886. |
[5] | 杨应科, 李东升, 沈立恒, 李汝鹏, 翟雨农. 大型复合材料机身壁板多机器人协同装配调姿控形方法[J]. 航空学报, 2023, 44(14): 428006-428006. |
[6] | 王涛, 高雪峰, 祝景萍, 董松, 孙连军, 郑侃. 机器人纵扭超声铣边颤振在线监测方法[J]. 航空学报, 2023, 44(13): 262-272. |
[7] | 刘传凯, 雷俊雄, 刘茜, 孙军, 苏建华, 胡晓东, 李东升. 基于逆投影的多椭圆联合快速高精度定位算法[J]. 航空学报, 2023, 44(12): 327731-327731. |
[8] | 董松, 郑侃, 孟丹, 廖文和, 孙连军. 大型复杂构件机器人制孔技术研究进展[J]. 航空学报, 2022, 43(5): 627133-627133. |
[9] | 廖文和, 田威, 李波, 李鹏程, 张苇, 李宇飞. 机器人精度补偿技术与应用进展[J]. 航空学报, 2022, 43(5): 627142-627142. |
[10] | 张加波, 刘海涛, 乐毅, 杨继之, 易茂斌, 王云鹏, 柔磊. 面向大型卫星的可移动混联机器人加工技术[J]. 航空学报, 2022, 43(5): 625731-625731. |
[11] | 王皓, 陈根良. 机器人型装备在航空装配中的应用现状与研究展望[J]. 航空学报, 2022, 43(5): 626128-626128. |
[12] | 田威, 程思渺, 李波, 廖文和. 考虑关节回差的工业机器人精度补偿方法[J]. 航空学报, 2022, 43(5): 625569-625569. |
[13] | 李宇飞, 田威, 李波, 张楠. 机器人铣削系统精度控制方法及试验[J]. 航空学报, 2022, 43(5): 625815-625815. |
[14] | 夏鹏程, 罗建军, 王明明, 谭龙玉. 空间双臂机器人抓捕非合作目标后的协调稳定控制[J]. 航空学报, 2022, 43(2): 325398-325398. |
[15] | 廖文和, 郑侃, 孙连军, 董松, 张磊. 大型复杂构件机器人加工稳定性研究进展[J]. 航空学报, 2022, 43(1): 26061-026061. |
阅读次数 | ||||||||||||||||||||||||||||||||||||||||||||||||||
全文 1206
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||
摘要 1633
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||
版权所有 © 航空学报编辑部
版权所有 © 2011航空学报杂志社
主管单位:中国科学技术协会 主办单位:中国航空学会 北京航空航天大学