第二讲：路径规划基础——图论基础与数学建模

各位同学，欢迎来到第二讲。

上一讲我们聊了AGV的整体架构，今天要进入一个绕不开的基础——图论。说实话，很多做AGV的朋友一听到“图论”两个字就头大，觉得是纯数学。但在我眼里，图论就是一张地图，加上一些规则。你想想看，AGV要走的车间地面，不就是一张图吗？

一、图论三要素：节点、边、权重

图论里最核心的东西，其实就三个词：节点、边、权重。我习惯把它们叫做“点、线、数”。

• 节点（Node/Vertex）：代表一个位置。比如AGV的充电站、工位、仓库入口。在代码里，我通常用一个整数或字符串来标识它。
• 边（Edge）：代表两个节点之间的连接。比如从A点到B点有一条路可以走。
• 权重（Weight）：代表走这条边的代价。可以是距离、时间、能耗，甚至风险值。

举个例子。我在一个汽车总装车间做项目时，地面有几十个工位。每个工位就是一个节点，工位之间的通道就是边。但注意，通道的权重不是简单的直线距离——因为有些通道经常有叉车经过，AGV得绕行或等待。所以我把“平均等待时间”也加进了权重里。

二、图的分类：有向图 vs 无向图

这里有个容易混淆的点。图分两种：有向图和无向图。

• 无向图：边没有方向。A到B和B到A的代价一样。比如车间里的双向通道。
• 有向图：边有方向。A到B和B到A可能是不同的路，甚至不存在反向路径。比如单行道、传送带方向。

我个人建议，在工业AGV场景里，尽量使用有向图。为什么？因为车间里很少有完全对称的路径。我曾经在一个仓库里吃过亏——用了无向图，结果AGV在窄通道里迎面撞上了另一台AGV。后来改成有向图，每条边只允许一个方向，问题就解决了。

三、路径规划问题的数学建模

好了，有了图，我们怎么把“找路”这件事变成数学问题？说白了，就是：给定一个图，找到从起点到终点的最优路径，使得总权重最小。

数学上可以写成这样：

给定图 G = (V, E, W)
其中 V 是节点集合
E 是边集合
W 是权重函数，W(e) > 0

求路径 P = {v0, v1, v2, ..., vk}
使得 v0 = start, vk = goal
且 sum(W(vi, vi+1)) 最小

嗯，看起来有点抽象。我换个说法：你站在车间东头，要去西头取货。中间有10条路可以走，每条路长度不同，有的路上还有障碍物。你要选一条总时间最短的路。这就是路径规划问题。

四、常见图结构在AGV中的应用

实际项目中，我们不会用那种乱七八糟的图。常用的就几种：

图结构	特点	适用场景
栅格图（Grid Map）	把地面分成小格子，每个格子是节点	室内仓库、有固定货架的区域
拓扑图（Topological Map）	只保留关键位置和连接关系	大型车间、走廊式环境
路网图（Roadmap）	类似城市道路网络	跨区域运输、多AGV协同

我记得有一次做半导体工厂的项目，车间里全是精密设备，AGV只能走固定的黄色通道。这时候用拓扑图最合适——节点就是通道交叉口，边就是通道段。简单、高效、不容易出错。

五、从图到代码：用Python表示图

讲理论不写代码，那是耍流氓。我习惯用Python的字典来表示图，简单直观。

# 用字典表示有向图
graph = {
    'A': {'B': 5, 'C': 3},
    'B': {'D': 2},
    'C': {'B': 1, 'D': 4},
    'D': {}
}

# 节点A到B的权重是5，A到C是3
# 注意：C到B是1，但B到C不存在（有向图）

你看，这个结构多清晰。键是起点，值是另一个字典，里面是终点和权重。我做了十年AGV，90%的路径规划代码都是用这种结构起步的。

如果你需要无向图，那就把双向边都加上：

# 无向图：A-B双向权重都是5
graph = {
    'A': {'B': 5},
    'B': {'A': 5}
}

六、路径规划问题的本质

最后，我想说一个观点。路径规划问题，本质上是一个优化问题。你不仅要找到一条路，还要找到“最好”的那条路。

什么叫“最好”？不同场景定义不同：

• 最短距离：适合空载AGV
• 最短时间：适合紧急任务
• 最低能耗：适合电量不足时
• 最少转弯：适合载有易碎物品

我做过一个项目，客户要求AGV运载液晶面板。面板很脆弱，转弯时容易晃动损坏。所以我把“转弯次数”作为主要权重，宁愿多走50米，也要少转两个弯。这就是权重设计的灵活性。

好，今天就到这里。记住：图是死的，权重是活的。多想想你的AGV到底在乎什么，比死磕算法更重要。