从 402 步到 26 步：一个 10×10 迷宫机器人的感知-决策-执行闭环改造

课程实验：具身智能导航（GridBot）。机器人只有 4 个即时传感器（前/左/右/后各一格），没有全局地图，只能一步一步走、一步一步看。

我的实验条件：学号尾号 4 → 禁用「左转」动作。所有调用「左转」的指令会被引擎静默忽略，并白白消耗一步。

代码量约 500 行，纯 Python 标准库（只用 heapq）。最终成绩：43/50，平均 26.4 步，15/15 全部通关，且零方差。

---

一、先说结论

指标	Baseline（随机策略）	我的版本	备注
平均步数	402.6（364~431）	26.4	快 15.3 倍
通关成功率	6.7/15（4~9）	15/15	100%
金币收集	45%	34%	唯一退步项，见第六节
自动评测总分	21.9/50（17~26）	43/50	步数 20/20 + 通关 15/15 满分
方差	每轮都不同	0	策略不含随机数

有三点值得单独强调，后面会展开：

1. Baseline 是随机策略，单次对比没有意义。 它每跑一轮分数都在 17~26 之间随机跳。我跑了 10 轮取均值才敢写"21.9 分"。如果你的报告里只贴了一次结果，答辩时被问"为什么换个机器分数就变了"会很难看。
2. 禁用动作是"空动作"，不是"报错"。 这是本实验最大的坑，也是我卡最久的地方。它的表现是"步数在涨、格子不动"，肉眼看像是程序死循环，实际是每一步都在发一条被丢弃的指令。
3. 把朝向纳入搜索状态，是解决"来回横跳"的唯一正解。 只按 (x, y) 建代价场，两个方向的估价会打平，机器人就在相邻两格之间反复跳。这个坑我踩了两次。

---

二、环境与接口

2.1 感知

每步拿到一个字典，四条相对方向 + 自身状态：

perception = {
    "front": "空地",    # 前方一格："空地"/"墙壁"/"金币"/"终点"/"边界"
    "left":  "墙壁",
    "right": "空地",
    "back":  "空地",
    "position": (3, 4),   # 当前坐标
    "target":   (9, 9),   # 终点坐标（这个给的是全局的，是唯一的外部信息）
    "direction": "南",    # 当前朝向
    "steps": 12,          # 累计步数
    "coins": 1,           # 已收集金币
    "memory": [...],      # 持久化记忆列表，跨步保留
}

注意 "边界" 的含义：它不是墙，而是相邻格子的坐标越界了（x<0 或 x>=10）。这一点后面会绊我一跤。

2.2 动作

decide(perception) 返回四个字符串之一："前进" / "左转" / "右转" / "后转"。

2.3 记忆

perception["memory"] 是同一个 list 对象在每步之间传递。这意味着：

# ✅ 正确：原地修改
memory[1][(x, y)] = "墙壁"
memory[2].add(pos)

# ❌ 错误：重新赋值
memory[1] = {...}   # 引擎下次给你的还是那个旧对象引用吗？不一定，别赌

我用 5 个槽位组织记忆：

memory[0] = "gridbot-v4"              # 初始化标记，防止跨局污染
memory[1] = {}                        # 已知地图 {(x,y): "空地"/"墙壁"/"金币"/"终点"}
memory[2] = set()                     # 走过的格子
memory[3] = set()                     # 已知不可走（撞过/边界）
memory[4] = {                         # 状态机
    "lastAction": "前进",
    "lastHeading": "南",
    "dead": [],                       # 已确认失灵的动作
    "pending": [],                    # 待执行的动作队列
}

---

三、为什么不用课本上的两个经典方法

实验指导里通常会推荐两条路：「右手法则」和「记录原始轨迹」。我都试过，都会崩。

3.1 右手法则：遇到带孤立柱子的地图就绕死

右手法则的前提是墙墙相连（完美迷宫）。本实验的地图里有孤立柱子，比如地图 4 的 (1,6)。机器人贴着柱子绕一圈，正好回到出发点，然后继续绕 —— 无限循环。

更根本的问题是：右手法则是一种局部策略，它不知道"我离终点还有多远"，所以无法判断"该不该为了这枚金币绕路"。而实验的评分有 35 分跟效率和金币挂钩。

3.2 记录原始轨迹：记了仇，但不知道往哪走

“这条路走过，不要再走” 是一种排除法，它只告诉你不能去哪，不告诉你该去哪。配上禁用的动作更糟：轨迹里会记下一连串"位置没变的动作"，机器人会误以为自己在一堆"死路"里，反而把自己锁死。

3.3 我选的路线：在线建图 + 全局代价场

思路来自传统的机器人导航栈（SLAM 前端 → 全局规划器 → 局部执行器），把它压缩进一个 decide() 函数里：

传感器 ──▶ 建图(memory) ──▶ 反向 Dijkstra 代价场 ──▶ 选方向 ──▶ 动作展开 ──▶ 指令队列
   ▲                                                                            │
   └──────────────────────────── 执行反馈 ◀──────────────────────────────────────┘

五层结构，下面按顺序讲，每一层都对应一个我实际踩到的坑。

---

四、第 1 层：在线建图（感知层）

没有上帝视角，地图一开始是空的。每步只能把四个传感器的读数写进记忆。

def _observe(perception, knownMap, blocked, pose):
    heading = pose[2]
    px, py = pose[0], pose[1]

    # 相对方向 → 绝对方向
    rel = {
        "front": heading,
        "back":  TURN_BACK[heading],
        "left":  TURN_LEFT[heading],
        "right": TURN_RIGHT[heading],
    }

    for key, absDir in rel.items():
        val = perception.get(key)
        if val is None:
            continue
        dx, dy = DELTA[absDir]
        cell = (px + dx, py + dy)

        # ★ 关键：边界格的坐标本来就出界，必须在这里处理
        if val == "边界":
            blocked.add(cell)     # 记进 blocked，不写 knownMap（它是非法坐标）
            continue

        if not (0 <= cell[0] < SIZE and 0 <= cell[1] < SIZE):
            blocked.add(cell)
            continue

        blocked.discard(cell)
        if val in BLOCK:
            knownMap[cell] = "墙壁"
            blocked.add(cell)
        else:
            knownMap[cell] = val

踩坑记录："边界" 必须最先处理

我最初写成这样：

if cell[0] < 0 or cell[0] >= SIZE or ...:
    continue                      # ← 越界就跳过
if val == "边界":
    blocked.add(cell)
    continue

看起来没问题，但 "边界" 的坐标本来就是越界的（比如站在 (0,9) 朝南，前方是 (0,10)）。所以第一个 continue 永远会先命中，blocked 里永远不会有它。

后果很隐蔽：机器人走到 (0,9) 之后，不知道前面走不通，一直在朝界外"前进"。表现和"禁用左转"的 bug 一模一样（步数涨、格子不动），害我白查了半天。

修复：把 if val == "边界" 提到越界判断之前。

---

五、第 2 层：带朝向的代价场（规划层）

5.1 反向 Dijkstra

从终点出发反向松弛，一次遍历就能算出全图每个格子"到终点还要几步"：

def _stepField(dest, knownMap, blocked, dead=()):
    field, heap = {}, []

    # 终点：任意朝向代价都是 0
    for d in ORDER:
        field[(dest[0], dest[1], d)] = 0.0
        heapq.heappush(heap, (0.0, dest[0], dest[1], d))

    while heap:
        cost, x, y, d = heapq.heappop(heap)
        if cost > field.get((x, y, d), 1e18) + 1e-9:
            continue

        # 反向 1：转向的逆操作
        for prevDir, turnCost in turnPrev(d):
            key = (x, y, prevDir)
            nc = cost + turnCost
            if nc < field.get(key, 1e18) - 1e-9:
                field[key] = nc
                heapq.heappush(heap, (nc, x, y, prevDir))

        # 反向 2：前进的逆操作
        dx, dy = DELTA[d]
        prev = (x - dx, y - dy)
        stepCost = _walkCost(prev, knownMap, blocked)
        if stepCost < FORBIDDEN:
            key = (prev[0], prev[1], d)
            nc = cost + stepCost
            if nc < field.get(key, 1e18) - 1e-9:
                field[key] = nc
                heapq.heappush(heap, (nc, prev[0], prev[1], d))

    return field

5.2 坑一：不判边界，进程直接卡死

第一版 _walkCost 长这样：

def _walkCost(cell, knownMap, blocked):
    if cell in blocked: return FORBIDDEN
    val = knownMap.get(cell)
    if val is None: return UNKNOWN_COST   # 迷雾：乐观估个 1.0
    ...

因为迷雾被打上 1.0 而不是 FORBIDDEN，Dijkstra 会一直往网格外扩散。10×10 的地图理论上应该只有 400 个状态，实际跑下去是无限多个 (x, y)，进程几分钟后吃满内存被杀掉。

我看日志里是 SIGTERM，还以为是沙箱超时，折腾了很久。

修复：_walkCost 第一行就判坐标边界。

def _walkCost(cell, knownMap, blocked):
    if not (0 <= cell[0] < SIZE and 0 <= cell[1] < SIZE):
        return FORBIDDEN      # ← 这一行救命
    ...

5.3 坑二：只按位置建场，机器人在两格之间横跳

这是我踩得最深的一个坑，而且修完以为好了，其实没好。

修完禁用左转之后，机器人在 (5,4) 和 (5,9) 之间来回跳。我把当时的估价打出来：

朝北站在 (5,4)：
  往东到 (6,4)  rest = 8.0
  往南到 (5,5)  rest = 8.0     ← 完全打平！

因为原来的 field 只按 (x, y) 建，完全没有转向成本。朝北站着时：

• “右转再往东走” = 1 步转向 + N 步前进
• “后转再往南走” = 2 步转向 + N 步前进

在只算位置的估价里，这两条路一样长，于是机器人随机左右跳。

修复：把状态从 (x, y) 扩展成 (x, y, 朝向)，转向 1 步、后转 2 步都进搜索成本。查询时也要对上朝向：

# ★ 查的是「走完这一步之后、朝向已经是 dirName」的估价
rest = field.get((nxt[0], nxt[1], dirName))

改成三元素状态后，横跳消失，步数还从 41 降到了 26。转向成本实际上帮它挑出了"转向更少"的路线。

---

六、第 3 层：金币激励（一个"调参失败"的教训）

金币格应当在路线选择时变便宜。我第一版的做法是：把金币格作为负成本水源塞进多源 Dijkstra。

结果整片估价被抹平了 —— 因为负成本会在反向松弛时传遍全图，起点往东、往南的代价几乎一样，机器人反而不愿为金币拐弯。

改成两层处理：

• 远处金币：靠全图步数场自然反映（走过去的距离）
• 踩上金币格那一步：享受一次性折扣

total = rest - centerBias + turnCost + walk + exploreTax + revisitFine

if knownMap.get(nxt) == "金币":
    total -= COIN_BONUS           # 5.0，约等于"这枚金币值 5 步路"

# 绕路预算：别为了 1 枚金币绕 50 步
allowance = COIN_BONUS + COIN_DETOUR + max(0, MAX_DETOUR - spent)
if total - goalCost > allowance:
    continue

调参踩的第二个坑：常数级罚分会被彻底淹没

机器人一开始总是贴着地图边缘直走（(0,0) → (0,9) → (9,9)），视野只覆盖边缘，金币率只有 33%。

我加了个"越靠场地中心越不着急"的偏好，想着让它走场地内部：

CENTER_TAX = 0.5
total += CENTER_TAX    # ❌ 完全没变化，连小数位都一样

打印四个方向的分数才明白：rest 一步就能差出 8，0.5 的罚分被彻底淹没。

修复：作用在距离量上，并放大到同一量级。

# 中心偏好，0~9 的连续量
distC = abs(nxt[0] - 4.5) + abs(nxt[1] - 4.5)
centerBias = 10.0 * (1.0 - distC / 9.0)
total = rest - centerBias + ...

改完金币率从 33% 提到 39%。

这一条是我觉得最值得写进文章的方法论：调参时先打印各分量的真实量级。如果你的启发式项和主项的差了一个数量级，它永远不会生效，你只会以为"这个想法没用"。

---

七、第 4 层：动作自检（本实验的核心难点）

学号尾号 4 → 禁用「左转」。

7.1 现象：步数在涨，格子不动

打开网页点"执行仿真"，右上角步数一路涨到 202，机器人却停在 (0,4) 一动不动。屏幕顶部有一行提示：“左转机构故障，调用『左转』将被忽略并浪费一步”。

去读引擎源码 game.py：

ctype = self.constraint.get("type")
if ctype == "action_disabled" and action == self.constraint["action"]:
    self.steps += 1
    return          # ← 只加步数，位置和朝向都不变

被禁用的动作是一个"空动作"，不是异常。

所以我的循环是这样死的：

1. 朝南，想到东边 → 返回 "左转"
2. 引擎忽略，steps += 1，朝向还是南
3. 下一步重新规划，朝向还是南，想到东边 → 又返回 "左转"
4. 回到第 2 步

死循环。而且因为 steps 在涨，看日志像是"在跑"，实际一步都没动。

7.2 第一步修复：自检

关键洞察：转向动作一定会改变朝向。所以对比"上一步发了什么"和"这一步朝向变没变"，就能判定动作为失灵。

def _selfCheck(pos, heading, st):
    dead = st["dead"]
    lastAct  = st["lastAction"]
    lastHead = st["lastHeading"]

    if lastAct and lastHead is not None:
        if lastAct == "左转" and heading == lastHead:
            if "左转" not in dead:
                dead.append("左转")       # 记仇，以后不再发
        elif lastAct == "右转" and heading == lastHead:
            if "右转" not in dead:
                dead.append("右转")
        elif lastAct == "后转" and heading == lastHead:
            if "后转" not in dead:
                dead.append("后转")
    return dead

注意："前进" 不能用朝向判断（前进本来就不改朝向），所以代码里没有对前进做推断。想检测"前进被禁用"得靠位置不变 + 前方不是墙，这个实验没这个条件，就不写了。

7.3 第二步修复：用可用动作组合达到任意朝向

知道左转坏了还不够，还得能转到东边。「右转 × 3」等价于「左转」。

def _expandAction(action, dead):
    if action not in dead:
        return [action]

    equiv = {
        "左转": [["右转","右转","右转"], ["后转","右转"], ["右转","后转"]],
        "右转": [["左转","左转","左转"], ["后转","左转"], ["左转","后转"]],
        "后转": [["右转","右转"], ["左转","左转"]],
    }
    for cand in equiv.get(action, []):
        if all(a not in dead for a in cand):
            return list(cand)
    return []

然后是"从当前朝向转到目标朝向要几步"的搜索。这里我写了两遍，第一遍是错的。

7.4 坑三：路径还原错了，机器人一步都不转

第一版我用 BFS 搜索朝向状态，队列里存"当前朝向"，最后再还原成动作序列：

# ❌ 错误版本
q = deque([(heading, [], 0)])
while q:
    cur, path, cost = q.popleft()
    for effect, stepCost in moves:
        nxt = effect[cur]
        npath = path + [cur]              # 存的是"上一个朝向"
        if nxt == targetDir:
            best = (npath + [cur], ncost) # 又塞了一个 cur ← 错位

还原的时候 for mid in pathDirs 把它当"目标朝向"用，于是第二个朝向开始就全错位了。

更要命的表现是：它返回了空列表。主循环拿到 moves = []，拼出的指令序列变成：

seq = [] + ["前进"]      # 等于"不转，直接前进"

于是机器人朝南站在 (0,9)、前方是边界，却不转向，一直撞墙。这个 bug 的表现和"禁用左转"几乎一样，我又查了很久。

修复：不要在最后还原，让队列直接携带已展开的动作序列。

def _turnPlan(heading, targetDir, dead):
    """用可用动作从 heading 转到 targetDir，返回 (动作列表, 真实步数)"""
    if heading == targetDir:
        return [], 0

    options = []
    for act, effect in (("左转", TURN_LEFT), ("右转", TURN_RIGHT), ("后转", TURN_BACK)):
        seq = _expandAction(act, dead)
        if seq:
            options.append((effect, seq))

    if not options:
        return None, 1e9

    # (累计步数, 当前朝向, 已展开的动作序列)
    pq = [(0, heading, [])]
    seen = {heading: 0}
    while pq:
        cost, cur, acts = heapq.heappop(pq)
        if cur == targetDir:
            return acts, cost          # 直接就是答案，不用还原
        if cost > seen.get(cur, 1e18) + 1e-9:
            continue
        for effect, seq in options:
            nxtDir = effect[cur]
            nc = cost + len(seq)
            if nc < seen.get(nxtDir, 1e18):
                seen[nxtDir] = nc
                heapq.heappush(pq, (nc, nxtDir, acts + seq))
    return None, 1e9

单测立刻通过：

>>> _turnPlan("南", "东", [])
(['左转'], 1)
>>> _turnPlan("南", "东", ["左转"])     # 左转坏了
(['后转', '右转'], 2)
>>> _turnPlan("南", "北", ["左转"])
(['后转'], 1)                          # 后转正好能到，不用绕

7.5 第三步修复：执行层用指令队列

前两步修完，还剩一个问题：机器人会在"转到一半"时改主意。

因为 decide() 每步都会被调用一次。如果它这步决定"先右转再前进"，返回 "右转" 之后引擎执行了，下一步重新规划时估价可能变了，于是它又想转回左边 —— 造成横跳。

解法：把"转向 + 前进"当成一条完整指令，排队执行完再重新规划。

# 有待执行的动作，先执行完
pending = st["pending"] or []
while pending:
    act = pending[0]
    if act in dead:              # 中途发现坏了，立刻放弃整条指令
        pending = []
        st["pending"] = []
        break
    st["pending"] = pending[1:]
    st["lastAction"] = act
    st["lastHeading"] = heading
    return act

# ... 规划 ...

seq = list(bestMoves) + ["前进"]
seq = [a for a in seq if a not in dead]
if not seq:
    seq = ["前进"]

st["pending"] = seq[1:]          # 剩下的排队
st["lastAction"] = seq[0]
return seq[0]

---

八、最终结果

8.1 分场景数据（禁用左转，我的真实条件）

场景	平均步数	金币率	通关
地图 1 — 新手村	27.0	67%	3/3
地图 2 — 小径	28.0	50%	3/3
地图 3 — 花园	25.0	20%	3/3
地图 4 — 迷宫入口	26.0	17%	3/3
地图 5 — 挑战迷宫	26.0	14%	3/3
合计	26.4	34%	15/15

评分明细：步数效率 20/20（满分）、通关成功 15/15（满分）、金币收集 8/15 → 总分 43/50。

8.2 禁用左转的代价几乎为零

条件	平均步数	总分
无约束（对照）	24.8	43
禁用左转（真实条件）	26.4	43

只多了 1.6 步。原因是：虽然「右转×3」比「左转」多花 2 步，但代价场会自动挑一条本来就少转向的路线把这点浪费吸收掉。

8.3 顺手测试了全部 10 种实验条件

把 constraints.py 里 10 种条件全跑了一遍：

尾号	条件	总分	步数效率	通关
0	左侧传感器故障	39	20/20	15/15
1	右侧传感器故障	43	20/20	15/15
2	后方传感器故障	43	20/20	15/15
3	禁用后转	43	20/20	15/15
4	禁用左转（我的）	43	20/20	15/15
5	步数上限 250	43	20/20	15/15
6	最少 3 枚金币	17	5/20	4/15
7	方向传感器恒为"北"	5	5/20	0/15
8	坐标恒为 (0,0)	31	15/20	12/15
9	禁用右转	43	20/20	15/15

前 6 种和尾号 9 都能拿 43 分。尾号 6、7、8 是我的方案的明确短板，见下一节。

---

九、诚实的短板

写技术文章最没意思的就是"我的方案完美"。这里说三个真实的上限。

9.1 金币率只有 34%，这是信息论上限，不是调参问题

我用 BFS 分析过：金币只有在走到相邻格（视野半径 1）时才能被发现。沿最短路走一遍，五张地图平均只能看到 1~2 枚金币。

想提高必须主动探索未知区域 —— 但探索要花步数，而步数占 20 分。这是一个真实的 POMDP 权衡，不是把 COIN_BONUS 调大就能解决的。

我试过 5 组参数：

COIN_BONUS / DETOUR / MAX_DETOUR	禁用左转总分	步数效率	金币率	平均步数
3 / 10 / 45	39	20/20	22%	24.8
5 / 14 / 60（采用）	43	20/20	34%	26.4
6 / 18 / 70	43	20/20	34%	26.4
8 / 22 / 80	43	20/20	38%	28.0

可以看到从 5 往上，金币率只从 34% 爬到 38%，步数却从 26.4 涨到 28.0，分数一分没多。这就是边际收益递减，所以最终选 5/14/60。

9.2 尾号 7、8 我会失败

• 尾号 7（direction 恒返回"北"）：我的代码直接信任 perception["direction"]，方向错了之后所有相对感知全部错位，整张地图画歪，0/15 通关。
• 尾号 8（position 恒返回 (0,0)）：同理，地图坐标全错。

正确解法是自己维护位姿：用"我上一步发了什么动作"推算朝向和坐标，再拿传感器做交叉校验。这属于真正的 SLAM 问题。

我试过加上这一层，结果把尾号 4 从 43 分拉到了 22 分（因为撞墙判定和位姿推算失配，产生漂移）。为了保证自己的实验条件不出错，我撤回了这个改动。

这是一个很实在的教训：不要为了修一个你不需要修的问题，去破坏当前能工作的方案。如果你要加容错层，务必单独回归测试原有条件。

9.3 性能没优化

每步都从终点重算一次全图代价场（10×10×4 = 400 个状态）。地图小所以无所谓，实测单局 27 步总共约 18ms。

如果地图放大到 100×100，这个做法会很慢。改进方向：A* 加曼哈顿启发、或者增量更新（只重算被新观测改变的格子）。

---

十、完整代码

my_bot.py 约 500 行，可直接运行。核心结构：

_ready(memory)                       记忆槽初始化（原地修改）
_observe(perception, ...)            建图：四传感器 → knownMap / blocked
_selfCheck(pos, heading, st)         动作自检：发现失灵动作
_expandAction(action, dead)          动作展开：左转坏了 → 右转×3
_turnPlan(heading, targetDir, dead)  转向规划：Dijkstra over 朝向
_walkCost(cell, ...)                 单格通行代价（判边界！）
_stepField(dest, ...)                带朝向的反向 Dijkstra 代价场
decide(perception)                   主入口

关键常数：

UNKNOWN_COST = 1.0    # 迷雾乐观估值
FINE_UNKNOWN = 1.2    # 走迷雾的"探索税"
FINE_REVISIT = 0.3    # 回头路罚款
COIN_BONUS   = 5.0    # 一枚金币值 5 步路
COIN_DETOUR  = 14     # 单枚最多绕 14 步
MAX_DETOUR   = 60     # 全程最多绕 60 步
CENTER_TAX   = 10.0   # 中心探索偏好

---

十一、六条可以直接抄走的经验

1. 禁用动作是空动作，不是异常。 如果任务里可能有"动作被静默丢弃"，一定要做动作-观测一致性自检：发了 A 动作，观测没变化 → A 失灵。这个思路在真实机器人上也成立（电机堵转、通信丢包）。

2. 状态空间要包含朝向。 凡是有转向成本的问题，只按 (x, y) 建代价场一定会横跳。加上朝向维度后不但不跳了，步数还更少。

3. 调参前先打印各分量的真实量级。 差一个数量级的启发式项等于没加。我被 CENTER_TAX = 0.5 骗过一次。

4. 搜索类函数不要把"还原路径"当第二步做。 让队列直接携带结果（动作序列），比存"前驱"再回溯少一半出错机会。我的 _turnPlan 就是因为二次还原错位，导致返回空列表。

5. 执行层要有指令队列。 每步重新规划 + 立刻执行 = 犹豫不决。把"转向+前进"打包执行完再规划，行为立刻稳下来。

6. 随机基线必须多次采样。 baseline 每轮 17~26 分随机跳，贴一次结果说"提升 N 倍"是不严谨的。跑 10 轮取均值，同时说明你的方案是确定性的（零方差）—— 这一点比倍数更有说服力。

---

附：环境说明

• Python 3.11，纯标准库（heapq），无第三方依赖
• 10×10 网格，5 张地图，每张跑 3 轮
• 评分：步数效率 20 + 金币收集 15 + 通关成功 15 = 50

---

本文所有数据来自实际运行，未做任何修饰。表格里的 baseline 数字是 10 轮均值，单轮结果会在标注范围内波动。