论文标题
计划的复杂性
Complexity of Planning
论文作者
论文摘要
这是机器人学百科全书中的一章。它致力于研究机器人运动计划的完整（或精确）算法的复杂性。 ``完整''一词表明一种方法可以保证找到正确的解决方案（在我们的设置中的运动路径或轨迹），或报告不存在其他情况（例如，如果不存在可行的路径）。复杂性理论是计算机科学的基本工具，用于分析算法的性能，从所需的资源数量来看。 （尽管复杂性可以表达不同数量的空间和沟通努力，但我们在本章中的重点是时间复杂性。）此外，复杂性理论有助于确定``硬''问题，这些问题需要过多的计算时间来解决。在运动计划的背景下，复杂性理论可以用各种方式派上用场，其中有些是在此处说明的。
This is a chapter in the Encyclopedia of Robotics. It is devoted to the study of complexity of complete (or exact) algorithms for robot motion planning. The term ``complete'' indicates that an approach is guaranteed to find the correct solution (a motion path or trajectory in our setting), or to report that none exists otherwise (in case that for instance, no feasible path exists). Complexity theory is a fundamental tool in computer science for analyzing the performance of algorithms, in terms of the amount of resources they require. (While complexity can express different quantities such as space and communication effort, our focus in this chapter is on time complexity.) Moreover, complexity theory helps to identify ``hard'' problems which require excessive amount of computation time to solve. In the context of motion planning, complexity theory can come in handy in various ways, some of which are illustrated here.
