运动规划的复杂性分析

# 运动规划的复杂性分析 ## 1. 运动规划问题概述 运动规划问题涉及寻找机器人在给定环境中从起始位置到目标位置的无碰撞路径。在解决这类问题时，算法的复杂度是一个关键考量因素。复杂度分析主要分为下界和上界两个方面，下界反映了问题本身的难度，而上界则由能解决该问题的算法所决定。 ## 2. 运动规划问题的下界 ### 2.1 基本概念 - **问题与算法的形式化**：问题被定义为一组实例，每个实例被编码为二进制字符串。算法通常被视为图灵机，它是一种可以在无界磁带上读写位的有限状态机。 - **语言与复杂度类**：语言是与问题相关的二进制字符串集合，代表问题的所有实例。复杂度类是在特定资源限制内可被解决的语言集合，常见的复杂度类包括 P、NP、PSPACE 和 EXPTIME。 - **P 类**：存在多项式时间算法的语言集合。 - **NP 类**：可由非确定性图灵机在多项式时间内解决的语言集合。 - **PSPACE 类**：在算法执行过程中，使用不超过多项式量级存储空间即可解决的语言集合。 - **EXPTIME 类**：可在时间 $O(2^{n^k})$（$k$ 为整数）内解决的语言集合。 ### 2.2 硬度与完备性 - **X - 硬**：若类 X 中的每个语言 B 都能在多项式时间内归约到语言 A，则称 A 为 X - 硬。 - **X - 完备**：若语言 A 既是 X - 硬，又属于类 X，则称 A 为 X - 完备。 ### 2.3 运动规划问题的下界实例 |问题描述|复杂度下界| | ---- | ---- | |一般运动规划问题（Formulation 4.1）|PSPACE - 完备| |仓库管理员问题（有限个平移矩形在矩形世界中）|PSPACE - 难| |Sokoban 问题（离散 2D 网格上的仓库管理员问题）|PSPACE - 难| |平面上链体的运动规划问题|PSPACE - 难| |3D 中链体在多面体障碍物间的运动规划问题|PSPACE - 难| |3D 多面体环境中机器人在不确定情况下的某种规划问题|NEXPTIME - 难| ### 2.4 下界的影响因素 下界或硬度结果显著依赖于问题的精确表示。例如，实例编码过长可能使问题看起来更容易；同时，问题表述中参数的变化也会影响结果。 ### 2.5 应对策略 面对较低的下界，有两种常见的应对策略： - **放宽要求**：容忍具有某种分辨率完备性或概率完备性的算法。 - **定义更窄的问题**：排除导致低下界的复杂构造，为这些较窄的问题设计高效算法。 ## 3. Davenport - Schinzel 序列 ### 3.1 定义 对于正整数 $n$ 和 $s$，一个 $(n, s)$ Davenport - Schinzel 序列 $(u_1, \ldots, u_m)$ 需满足以下条件： - 序列中相同符号不能连续出现，即对于 $1 \leq i < m$，有 $u_i \neq u_{i + 1}$。 - 序列不包含使用两个符号且长度为 $s + 2$ 的交替子序列。 ### 3.2 与函数包络的关系 考虑一组实值连续函数，若已知每对函数最多相交 $s$ 次，那么访问这些函数下包络的函数索引序列就是一个 $(n, s)$ Davenport - Schinzel 序列。 ### 3.3 标准界 - $\lambda_1(n) = n$ - $\lambda_2(n) = 2n - 1$ - $\lambda_3(n) = \Theta(n\alpha(n))$ - $\lambda_4(n) = \Theta(n \cdot 2^{\alpha(n)})$ - $\lambda_{2s}(n)