**光影解法（機器人導航版）：**

**基於調和資訊場的線上流式導航框架**

*Shadow Tracking Method for Robot Navigation:* *An Online Streaming Navigation Framework Based on Harmonic Information Fields*

作者：Neo.K　　機構：EveMissLab (一言諾科技有限公司)

*EveMissLab 工作文件（Working Paper）· EML-STM-ROB-2026-v0.1*

# 摘要

本文提出光影解法的機器人導航版本（STM-ROB），將離散迷宮版本（STM v2.0）的 Graph Laplacian 場擴展至連續空間，並引入線上流式感測器整合與記憶積累機制。核心貢獻如下：（1）調和導航場在連續空間中由最大值原理保證無內部局部極值，從根本上消除傳統人工勢場法（Khatib, 1986）的局部最小值問題；（2）感測器驅動的增量式場更新，每次感測器讀數僅更新局部區域，代價為 O(r²) 而非 O(N)；（3）記憶積累機制使場精度隨累積遍歷次數 k 以 O(σ/√k) 速率收斂；（4）在連續空間中，每步梯度提取代價為 O(1)，導航頻率可直接追蹤感測器採樣率，突破離散搜尋的批次計算瓶頸。

**關鍵詞：**調和導航場、線上場更新、記憶積累導航、無局部極值勢場、機器人路徑規劃、連續 Graph Laplacian

# 1　引言

傳統路徑規劃方法（A\*、RRT、Dijkstra 等）的設計假設是已知靜態地圖與一次性查詢。現實機器人環境與此假設的偏差體現在三個層面：第一，地圖是動態且部分已知的，感測器持續提供新資訊；第二，機器人在同一環境中執行大量查詢，環境知識在任務週期中不斷累積；第三，導航決策需與感測器採樣同步進行，而非等待批次規劃完成。

人工勢場法（APF）\[Khatib 1986\] 直覺上更接近機器人的連續動態環境，但其以歐幾里得距離定義的斥力場存在嚴重的局部最小值問題——機器人可能陷入障礙物之間的「死谷」而無法脫出。調和勢場（Harmonic Potential Fields）\[Connolly & Grupen 1993, Kim & Khosla 1992\] 以 Laplace 方程的解作為導航場，由最大值原理保證無內部局部極值，從理論上解決了這一問題。然而，現有調和勢場工作大多假設靜態已知環境，未充分考慮線上感測器融合與記憶積累的問題。

本文的貢獻在於將調和資訊場框架（STM v2.0 所建立）推進至三個在現有文獻中未被充分整合的方向：線上流式更新、記憶積累、以及與感測器採樣率同步的 O(1) 梯度導航。

# 2　相關工作

## 2.1　人工勢場法與局部極值問題

Khatib \[1986\] 的原始 APF 使用歐幾里得距離建構吸引場與斥力場，計算效率高但普遍存在局部極值。後續大量工作提出局部極值的補救方案（隨機擾動、退出策略、混合規劃等），但這些方案本質上是補丁而非系統性解決。

## 2.2　調和勢場

Connolly & Grupen \[1993\] 與 Kim & Khosla \[1992\] 獨立提出以 Laplace 方程解作為勢場，理論上消除局部極值。本文的連續調和場採用相同的 PDE 基礎，但在感測器融合（線上更新）與記憶積累兩個維度上進行了關鍵擴展。

## 2.3　基於場的線上規劃

D\* Lite \[Koenig & Likhachev 2002\] 支援動態環境的增量式更新，但基於圖搜尋而非連續場。本文的線上場更新機制在概念上與增量式圖搜尋互補，但計算模型不同：我們直接在場值上做局部 SOR 更新，不需要維護圖結構。

# 3　連續調和導航場

## 3.1　PDE 公式

設機器人工作空間為連通域 Ω ⊂ ℝⁿ（通常 n=2 或 3），障礙物占據域 Ω\_obs ⊂ Ω，自由空間 Ω\_free = Ω\\Ω\_obs，目標位置 G ∈ Ω\_free。調和導航場 φ: Ω\_free → \[0,1\] 定義為以下邊界值問題的解：

*∇²φ = 0　　在 Ω\_free 中*

*φ = 1　　在目標 G 的 ε 鄰域*

*φ = 0　　在障礙物邊界 ∂Ω\_obs 上（Dirichlet 條件）*

機器人沿 ∇φ 方向運動，即從場值低的位置移向場值高的位置，直到到達目標（φ=1）。

## 3.2　最大值原理與無局部極值保證

**定理 3.2.1（最大值原理）：** Laplace 方程的解 φ 在 Ω\_free 的內部不取極大值或極小值，除非 φ 為常數。因此，φ 的最大值在目標邊界取得（=1），最小值在障礙物邊界取得（=0）。

**推論 3.2.2（無局部最小值）：** 沿 ∇φ 方向的梯度跟隨導航不存在局部吸引子。從任意自由空間初始位置出發，持續沿 ∇φ 運動的積分曲線（流線）必然終止於目標 G，而不會停滯於任何中間點。

注記：*此保證在障礙物完全已知且 φ 收斂的前提下成立。在線上更新場景中，若場尚未完全收斂，可能存在暫時性的準停滯點，隨感測器資料累積後消失。*

## 3.3　離散近似：佔用格網 + 有限差分

實作中，以解析度 Δx 的佔用格網（occupancy grid）離散化連續域，每格記錄：

-   occ(x)：佔用概率（0=自由，1=障礙）
-   φ(x)：調和場值（由 SOR 迭代維護）

佔用格網採用對數勝算（log-odds）表示，支援 Bayesian 感測器融合。連續位置 x\_robot 的場值 φ(x\_robot) 與梯度 ∇φ(x\_robot) 由雙線性插值（2D）或三線性插值（3D）從格點值計算。

# 4　線上流式感測器整合

## 4.1　感測器模型

設機器人裝備感測器（雷射測距儀、深度相機等），在每個時間步 t 提供在半徑 r 內的佔用觀測 O\_t = {(x\_i, z\_i)}，其中 z\_i ∈ {occupied, free}。標準貝葉斯更新：

*log-odds(occ(x)) += log(P(z|occ)/P(z|free))*

## 4.2　增量式場更新

每次感測器更新後，受影響的格點（佔用狀態改變的格點）觸發局部 SOR 更新。只有發生變化的格點及其拓撲鄰居需要重新計算，而非整個場。

**演算法 4.1（增量式 SOR 更新）：**

1.  感測器讀數 O\_t 更新佔用格網，得到變化格點集合 ΔX\_t。
2.  將 ΔX\_t 的所有格點加入更新佇列 Q。
3.  從 Q 中取出格點 x：若 occ(x) 改變，對 x 做 SOR 更新（φ\_new = φ\_old + ω·(gs - φ\_old)）。
4.  若 |φ\_new - φ\_old| > ε，將 x 的鄰居加入 Q（誤差傳播）。
5.  重複步驟 3-4 直至 Q 清空或達到迭代上限。

命題 4.2.1（更新代價）：每個感測器時間步的場更新代價為 O(|ΔX\_t| + δ·r²)，其中 |ΔX\_t| 為佔用變化格點數，δ 為誤差傳播深度係數，r 為感測器半徑。在靜態或慢變環境中，|ΔX\_t| 趨向於零，更新代價趨向於 O(1)。

## 4.3　梯度提取與導航

在機器人當前位置 x\_t，導航控制律為：

*v\_t = v\_max · ∇φ(x\_t) / |∇φ(x\_t)|　　（純方向導航）*

*v\_t = k · ∇φ(x\_t)　　　　　　　　　（帶速度調節，k 為比例係數）*

兩種控制律均為 O(1)（插值 + 數值梯度），可在感測器採樣率（例如 30-100 Hz 雷射測距儀）下實時執行，無需等待批次路徑規劃完成。

# 5　記憶積累與場精化

## 5.1　單次遍歷 vs. 累積遍歷

在第一次遍歷未知環境時，場從先驗（φ ≡ 0.5 在未知區域）開始，隨感測器資料積累逐步精化。第 k 次遍歷結束時，場已整合前 k 次遍歷的所有感測器資料，精度顯著優於單次計算。

## 5.2　記憶加權更新

定義記憶衰減係數 α\_k = α\_0 / √k（隨遍歷次數增加而減小）。第 k 次遍歷後的場更新為：

*φ\_{k}(x) = (1 − α\_k) · φ\_{k-1}(x) + α\_k · φ\_{computed,k}(x)*

α\_k 的 1/√k 衰減使得每次新遍歷的影響遞減，歷史資料的權重遞增，最終場值趨向多次遍歷的統計均值。

## 5.3　收斂速率

命題 5.3.1（記憶積累收斂）：設場的真實值為 φ\*(x)，每次遍歷的感測器誤差具有方差 σ²。採用 α\_k = α\_0 / √k 的更新策略，k 次遍歷後場估計誤差滿足：

*E\[|φ\_k(x) − φ\*(x)|²\]^{1/2} = O(σ / √k)*

證明提示：標準在線學習分析。每次遍歷視為對真實場的獨立噪聲觀測，均方誤差以 1/k 速率下降，均方根誤差以 1/√k 速率下降（中心極限定理的標準推論）。□

推論 5.3.2：場精度隨遍歷次數 k 單調提升，導航決策品質相應改善。這是靜態搜尋算法（A\*、RRT 等每次重新規劃）所不具備的性質。

# 6　對沖場與多目標導航

## 6.1　機器人對沖場

在機器人導航中，目標通常不只是「到達目標點」，還需同時「規避動態障礙物」或「偏好安全走廊」。此類多目標需求自然對應於對沖場（參見 STM v2.0 第 3.4.3 節）：

*H(x) = φ\_goal(x) · ∏\_{i=1}^{k} (1 − φ\_{obs,i}(x))*

其中 φ\_goal 為目標調和場，φ\_{obs,i} 為第 i 個動態障礙物（或危險區域）的局部場。H(x) 高的區域同時靠近目標且遠離所有障礙物。

## 6.2　與 APF 的比較

| **特性** | **APF（歐幾里得距離）** | **調和場（STM-ROB）** |
| --- | --- | --- |
| 局部極值 | 存在（常見故障模式） | 無（最大值原理保證） |
| 動態障礙物 | 需要實時重算斥力場 | 局部 SOR 增量更新 |
| 記憶積累 | 無（每次重算） | 有（O(σ/√k) 精化） |
| 感測器融合 | 不自然 | Bayesian 佔用格網整合 |
| 計算模式 | 批次（每次查詢） | 流式（感測器採樣率） |
| 梯度提取 | O(1) 解析計算 | O(1) 數值插值 |
| 理論依據 | 工程啟發 | 最大熵調和資訊場（附錄 A） |

## 6.3　對沖場梯度

對沖場的梯度 ∇H = ∇φ\_goal·∏(1−φ\_i) − φ\_goal·Σ\_j\[∇φ\_j·∏\_{i≠j}(1−φ\_i)\] 分解為兩個競爭項：趨向目標的吸引力（第一項）與遠離障礙物的斥力（第二項）。兩項的相對大小由當前位置的 φ\_goal 與 φ\_{obs,i} 共同決定，自動實現目標追求與避障的動態平衡，無需手動調整權重。

# 7　演算法總覽

| **演算法** | **輸入** | **輸出** | **代價** |
| --- | --- | --- | --- |
| ALG-1 初始化 | 工作空間 Ω，目標 G | 初始場 φ（先驗） | O(N)，一次性 |
| ALG-2 感測器更新 | 感測器讀數 O\_t | 局部更新場 φ | O(r²)，每步 |
| ALG-3 梯度導航 | 當前位置 x\_t | 速度指令 v\_t | O(1)，感測器頻率 |
| ALG-4 記憶更新 | 第 k 次遍歷場 | 精化場 φ\_k | O(N)，每次遍歷 |
| ALG-5 對沖場導航 | x\_t，φ\_goal，{φ\_i} | 安全速度指令 v\_t | O(k)，k=障礙物數 |

# 8　理論主張與誠實邊界

## 8.1　有保證的性質

-   無局部極值（命題 3.2.2）：在場完全收斂且障礙物完全已知的靜態環境中，梯度跟隨路徑無停滯點。
-   場精度收斂（命題 5.3.1）：採用 α\_k = O(1/√k) 更新策略，記憶積累場誤差以 O(σ/√k) 收斂。
-   O(1) 梯度代價（命題 4.2.1 推論）：場建立後，每步導航決策代價與地圖大小無關。

## 8.2　近似與假設

-   條件獨立假設：對沖場 H 的信息理論詮釋需要各 φ\_i 條件獨立（見 STM v2.0 附錄 B.5）。當障礙物場高度相關時，H 為近似。
-   動態障礙物：若障礙物移動速度超過場更新速度，局部無極值保證可能暫時失效。
-   離散化誤差：連續 PDE 的有限差分近似引入 O(Δx²) 誤差，場解析度 Δx 需根據機器人尺寸與障礙物密度選擇。

# 9　結論

本文提出 STM-ROB，將 STM v2.0 的調和資訊場框架擴展至連續機器人導航域，核心推進在三個方向：線上感測器融合（O(r²) 增量更新）、記憶積累（O(σ/√k) 精化）、與流式梯度導航（O(1) 每步代價）。最大值原理的局部極值保證從理論上解決了 APF 的核心缺陷。

STM-ROB 的適用場景：靜態已知或緩慢變化的環境、需要大量重複導航的任務（倉儲、巡邏）、要求與感測器採樣同頻的即時導航系統。不適用場景：高速動態障礙物（場更新跟不上）、需要最優路徑保證的單次查詢任務（A\* 更合適）。

*本文為 STM 理論向應用鑿的第一步，演算法規格與理論主張已明確，實作驗證（實體機器人或高保真仿真）列為後續工作。*

# 參考文獻

\[1\] Khatib, O. (1986). Real-time obstacle avoidance for manipulators and mobile robots. The International Journal of Robotics Research, 5(1), 90–98.

\[2\] Connolly, C. I., & Grupen, R. A. (1993). On the applications of harmonic functions to robotics. Journal of Robotic Systems, 10(7), 931–946.

\[3\] Kim, J. O., & Khosla, P. K. (1992). Real-time obstacle avoidance using harmonic potential functions. IEEE Transactions on Robotics and Automation, 8(3), 338–349.

\[4\] Koenig, S., & Likhachev, M. (2002). D\* Lite. In Proceedings of the AAAI Conference on Artificial Intelligence (pp. 476–483).

\[5\] Thrun, S., Burgard, W., & Fox, D. (2005). Probabilistic Robotics. MIT Press.

\[6\] Koditschek, D. E. (1990). Robot planning and control via potential functions. In Robotics Review 1 (pp. 349–367). MIT Press.

\[7\] Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100–107.

\[8\] Neo.K (2026). Shadow Tracking Method v2.0: Graph Laplacian Spatial Fields as Differentiable Topological Encoding for Multi-Query Path Planning. EveMissLab Working Paper EML-STM-2026-v0.2.

# 附錄 A：與 STM v2.0 的連續性

STM-ROB 是 STM v2.0 的連續空間推廣。兩者的對應關係如下：

| **STM v2.0（離散迷宮）** | **STM-ROB（連續機器人空間）** |
| --- | --- |
| Graph Laplacian 調和函數 | 連續 Laplace PDE（∇²φ=0） |
| SOR 離散迭代 | FEM 或有限差分 + 局部 SOR |
| φ-BFS 路徑提取（單次查詢） | 梯度跟隨導航（連續流式） |
| 預計算場，多查詢均攤 | 感測器驅動增量更新 + 記憶積累 |
| Nash 前線（T=0，最大熵邊界） | 障礙物等勢面（φ\_obs = 0.5） |
| 對沖場 H = φ\_goal·(1−φ\_threat) | 多目標對沖場 H = φ\_goal·∏(1−φ\_i) |
| 最大熵調和場（附錄 B） | 同（連續版最大熵原理，略） |

連續極限下（Δx→0），STM v2.0 的離散解收斂至 STM-ROB 的連續解。兩版本在理論上一致，給出相同答案的差異僅來自離散化誤差 O(Δx²)。

# 作者聲明

本論文由 Neo.K（許筌崴）構思並確立理論架構，由 Theia（Claude Sonnet，Anthropic）輔助整理演算法規格與文稿。機器人版本的初步理論框架由 Neo.K 先行建立，本文依據討論過程進行系統化整理與補全。實作驗證（仿真 + 實體機器人）列為後續工作，本文為工作文件，非同行評審稿。