第2章空间建模基础

空间建模基础：构型空间（C-Space）概念、障碍物表示方法、自由空间与可行域

大家好，欢迎来到航迹规划的第一章。

说实话，很多新手一上来就急着调算法、跑路径，结果连最基本的空间建模都没搞明白。我当年也犯过这个错——在栅格地图上跑A*，跑出来一条贴着墙根的路径，机器人根本走不了。后来才意识到，问题出在空间建模上。

这一章，我们就来把地基打牢。

1. 构型空间（C-Space）——规划师的“画布”

先问一个问题：你的机器人是一个点吗？

当然不是。它有尺寸、有形状、可能还有关节。但在规划路径时，我们能不能把它当成一个点来处理？

能。这就是构型空间（Configuration Space，简称C-Space）的核心思想。

说白了，C-Space就是把机器人的所有可能状态（位置、角度、关节角等）映射到一个抽象空间里。在这个空间里，机器人被缩成一个点，障碍物被“膨胀”成新的形状。

举个例子。你有一个圆形机器人，半径0.5米，在二维平面上移动。它的构型就是(x, y)坐标。C-Space就是所有(x, y)的集合。障碍物呢？每个障碍物向外扩展0.5米，就变成了C-Space里的障碍物。

这样做的好处很明显：

简化问题：点机器人的路径规划，比有形状的机器人简单得多
统一处理：不管机器人长什么样，最后都变成点
数学优雅：可以用拓扑学、微分几何等工具分析

核心公式：C-Space = 所有构型的集合。对于二维移动机器人，C = R² × S¹（位置+朝向）。

我在做仓储机器人项目时，就吃过C-Space的亏。当时直接用了原始地图做规划，结果机器人总在狭窄通道里卡住。后来把机器人轮廓考虑进去，膨胀了障碍物，问题就解决了。

3. 障碍物表示方法——三种主流思路

有了C-Space的概念，接下来就是怎么表示障碍物。我常用的方法有三种：栅格法、几何法、拓扑法。每种都有它的脾气。

3.1 栅格法——简单粗暴，适合新手

栅格法就是把空间切成一个个小格子。每个格子要么是自由（0），要么是障碍（1）。

优点？实现简单，理解容易。缺点？分辨率高了内存爆炸，分辨率低了路径不精确。

// 栅格地图示例（C语言风格伪代码）
#define GRID_WIDTH 100
#define GRID_HEIGHT 100
int grid[GRID_WIDTH][GRID_HEIGHT];

// 初始化所有格子为自由空间
for (int i = 0; i < GRID_WIDTH; i++) {
    for (int j = 0; j < GRID_HEIGHT; j++) {
        grid[i][j] = 0; // 0表示自由
    }
}

// 标记障碍物
void mark_obstacle(int x, int y, int radius) {
    for (int i = x - radius; i <= x + radius; i++) {
        for (int j = y - radius; j <= y + radius; j++) {
            if (i >= 0 && i < GRID_WIDTH && j >= 0 && j < GRID_HEIGHT) {
                grid[i][j] = 1; // 1表示障碍
            }
        }
    }
}

我的经验：栅格大小取机器人直径的1/3到1/2比较合适。太小了计算慢，太大了路径质量差。

3.2 几何法——精确但复杂

几何法用基本几何形状（矩形、圆形、多边形）来描述障碍物。适合结构化环境，比如室内、工厂。

我记得有一次做无人机航迹规划，障碍物都是建筑物。用栅格法？内存根本扛不住。换成几何法，每个建筑物用一个多边形表示，规划速度快了10倍。

// 几何障碍物表示示例（Python风格）
class Obstacle:
    def __init__(self, vertices):
        self.vertices = vertices  # 多边形顶点列表
        self.type = "polygon"
    
    def contains_point(self, point):
        # 射线法判断点是否在多边形内
        # 具体实现略...
        pass

# 创建一个矩形障碍物
rect_obs = Obstacle([(0,0), (10,0), (10,5), (0,5)])

几何法的核心是碰撞检测。常用的算法有：

分离轴定理（SAT）：检测凸多边形是否相交
GJK算法：更高效的凸体碰撞检测
包围盒层次（BVH）：加速复杂场景的碰撞查询

避坑指南：我曾经在项目中直接用精确几何模型做碰撞检测，结果每帧要检测上千个多边形，帧率掉到个位数。后来用了BVH加速，才把性能拉回来。

3.3 拓扑法——抓大放小

拓扑法不关心精确的几何形状，只关心空间的连通关系。说白了，就是“哪里能走，哪里不能走”。

这种方法适合大规模、稀疏的环境。比如城市道路规划，你不需要知道每栋楼的精确位置，只需要知道哪些街道是通的。

拓扑图通常用图（Graph）来表示：

节点：关键位置（路口、地标）
边：可通行的路径
权重：距离、时间、能耗等

// 拓扑地图示例
class TopoMap:
    def __init__(self):
        self.nodes = {}  # 节点ID -> 位置
        self.edges = []  # (节点A, 节点B, 权重)
    
    def add_node(self, node_id, position):
        self.nodes[node_id] = position
    
    def add_edge(self, node_a, node_b, weight):
        self.edges.append((node_a, node_b, weight))

4. 自由空间与可行域——规划的核心

有了C-Space和障碍物表示，接下来就是找出“能走的地方”。

自由空间（Free Space）就是C-Space中所有非障碍区域的集合。说白了，就是机器人能去的所有位置。

可行域（Feasible Region）则更严格——它不仅要求位置可行，还要求运动学约束、动力学约束、时间约束等都能满足。

举个例子。你的机器人能原地转弯吗？如果能，自由空间就是可行域。如果不能（比如汽车不能原地掉头），那可行域就比自由空间小得多。

关键区别：自由空间只考虑“能不能放得下”，可行域考虑“能不能开过去”。

我在做AGV（自动导引车）项目时，就遇到过这个问题。自由空间明明很宽敞，但AGV转弯半径太大，很多地方进得去出不来。后来在规划时加入了转弯半径约束，才真正解决了问题。

5. 本章知识体系总览

下面这张图，是我自己总结的空间建模知识框架。你可以把它当成一张“地图”，随时回来对照。

6. 小结

这一章我们聊了空间建模的三个核心概念：

C-Space：把机器人缩成点，把世界重新映射
障碍物表示：栅格法简单、几何法精确、拓扑法高效
自由空间与可行域：能放得下 vs 能开过去

嗯，这些概念看起来简单，但真正用好需要大量实践。我建议你找个开源地图，试着用三种方法分别建模，感受一下它们的区别。

下一章，我们会把这些概念串起来，开始讲具体的路径搜索算法。到时候你会发现，今天打的地基有多重要。

📚 课程目录

空间建模基础：构型空间（C-Space）概念、障碍物表示方法、自由空间与可行域

1. 构型空间（C-Space）——规划师的“画布”

3. 障碍物表示方法——三种主流思路

3.1 栅格法——简单粗暴，适合新手

3.2 几何法——精确但复杂

3.3 拓扑法——抓大放小

4. 自由空间与可行域——规划的核心

5. 本章知识体系总览

6. 小结