失而復得：Archimedean 螺旋與失物搜尋路徑

封存文章

本文是 100 × 100 呎公園失物搜尋的教學模型。舊版直接稱固定螺旋為「最優」，但沒有比較其他路徑，螺旋圈距亦大於燈光覆蓋寬度，而刪除障礙物內節點會造成不連續跳躍。本版本改以 probability of detection 為目標，並提供可驗證的路徑設計。

假設一枚戒指可能掉在 $100\times100$ 呎的公園，天色昏暗，搜尋者有手電筒、兩小時和若干障礙物。真正的決策不是「哪條曲線漂亮」，而是：

在失物位置的先驗分布、視野、步速、障礙物與時間限制下，哪條連續可行路徑能最大化找到失物的概率？

一、搜尋模型

令搜尋區域為 $\Omega\subset\mathbb R^2$ ，障礙物區域為 $\mathcal O$ ，可搜尋區為

\Omega_f=\Omega\setminus\mathcal O.

路徑 $\gamma:[0,T]\to\Omega_f$ 必須滿足速度限制

\|\dot\gamma(t)\|\le v(\gamma(t)).

失物位置 $X$ 的 prior density 為 $\pi(x)$ 。如果確信物件在某個最後見到位置附近， $\pi$ 可集中於該處；若完全沒有資訊，才可能近似 uniform。

偵測函數

距離路徑 $d$ 的單次偵測概率可用

p_{\rm det}(d) =p_0\exp(-d/R),

但 $R$ 應由手電筒、目標尺寸、地面材質和步速的 field test 估計。舊文把這個函數稱為「光效」，但照度的物理 inverse-square law、人眼偵測和遮擋不是同一件事；把它當成 empirical detection curve 更恰當。

若網格 cell $x$ 被多次近距離經過，獨立 detection attempt 假設下：

P_{\rm det}(x\mid\gamma) =1-\prod_{k} \left[1-p_{\rm det}(d_{xk})\right].

整體成功概率是

P_{\rm find}(\gamma) =\int_{\Omega_f} \pi(x)P_{\rm det}(x\mid\gamma)\,dx.

這個目標同時處理先驗位置和重複搜尋；單純 binary coverage ratio 則兩者都看不到。

二、Archimedean 螺旋的幾何

以中心 $(x_c,y_c)$ 為起點：

r(\theta)=r_0+a\theta,

\begin{aligned} x(\theta)&=x_c+r(\theta)\cos\theta,\\ y(\theta)&=y_c+r(\theta)\sin\theta. \end{aligned}

相鄰兩圈的徑向間距是

\Delta r=2\pi a.

如果有效搜尋半寬為 $R_{\rm eff}$ ，要避免筆直地形上的條帶缺口，通常需

2\pi a\le2R_{\rm eff}, \qquad a\le\frac{R_{\rm eff}}{\pi}.

舊版使用 $a=2$ 、 $R_{\rm eff}=2$ 呎；圈距為 $4\pi\approx12.57$ 呎，遠大於 4 呎總覆蓋寬，所以「不留空白」並不成立。

路徑長度

螺旋由 $\theta_0$ 至 $\theta_1$ 的長度為

L =\int_{\theta_0}^{\theta_1} \sqrt{r(\theta)^2+\left(\frac{dr}{d\theta}\right)^2}\,d\theta =\int_{\theta_0}^{\theta_1} \sqrt{(r_0+a\theta)^2+a^2}\,d\theta.

它可用解析 antiderivative 或 numerical quadrature 計算。設定 $\theta\in[0,15\pi]$ 、 $a=2$ 會令最大半徑約 95 呎；由 50 呎中心出發，多數外圈已超出方形公園。刪除越界點並不會自動產生可走路徑。

三、速度與時間的單位檢查

舊參數把步速設為 4 mph：

4\times\frac{5280}{60}=352\ {\rm ft/min}.

兩小時可走 42,240 呎，而公園只有 100 呎寬。這是普通步行速度，不是彎腰用小燈仔細找戒指的有效搜尋速度。若 path spacing 是 4 呎，理想 lawnmower path 覆蓋一萬平方呎約需

L\approx\frac{A}{2R} =\frac{10{,}000}{4} =2{,}500\ {\rm ft},

但轉彎、障礙物與檢視會增加時間。應用 pilot test 量度「保持目標 detection rate 時的速度」，而不是直接用正常步速。

四、障礙物處理

一個點安全的條件是

\min_{o\in\mathcal O}d(x,o)\ge d_{\rm safe}.

因此「無效」應是距離小於安全值；舊文字的不等號方向寫反。

更重要的是，以下做法不安全：

valid_points = [point for point in spiral if is_valid(point)]

它只刪除障礙物內的點，然後用直線連接刪除前後兩點；線段仍可能穿過障礙物，甚至在相距很遠的邊界片段間跳躍。正確做法是：

將障礙物按搜尋者半徑作 configuration-space inflation；
偵測 path segment 與 inflated obstacle 的相交；
在相交處以 visibility graph、A* 或 boundary-following detour 連接；
把 detour 長度和額外 overlap 計入目標。

def segment_is_free(a, b, obstacle_mask, samples=100):
    points = np.linspace(a, b, samples)
    ij = np.rint(points).astype(int)
    return not obstacle_mask[ij[:, 0], ij[:, 1]].any()

production implementation 應使用連續幾何庫，而不是只抽樣 100 點。

五、三種基準路徑

在宣布螺旋優勝前，至少要比較：

1. Lawnmower／boustrophedon

平行條帶的間距可設為 $2R_{\rm eff}$ 。它對 uniform prior 和矩形開放區域通常有高覆蓋效率，而且容易驗證漏帶。

2. 由中心向外的螺旋

若 prior 集中在中心，螺旋會優先掃描高概率區，路徑連續、轉向平滑。若 prior uniform，外圍最後才搜可能沒有優勢。

3. 概率引導路徑

把區域分成 cells，以 expected marginal detection gain 選下一個區域：

\Delta V_j =\frac{ \sum_{x\in j} \pi(x) \left[P_{\rm new}(x)-P_{\rm old}(x)\right] }{ \text{travel time to }j+\text{search time in }j }.

這是 greedy baseline；更完整可表成 orienteering／coverage path planning problem。

六、離散覆蓋計算

在 1 呎網格上，對每個 cell 求到整條 polyline 的最短距離，而不是只求到稀疏 path vertices 的距離：

d(x,\gamma)=\min_{s\in[0,T]}\|x-\gamma(s)\|.

binary coverage 為

C_\tau = \frac{ \sum_{x\in\Omega_f} \mathbf1[p_{\rm det}(d(x,\gamma))\ge\tau] }{ |\Omega_f| }.

分子和分母必須同樣限制在 $\Omega_f$ 。舊程式分母排除 terrain difficulty ≥ 0.8，分子卻計入障礙物上方 coverage，可能令效率偏高。

若沿路徑以細 segments rasterize，可用 distance transform：

import numpy as np
from scipy.ndimage import distance_transform_edt

def coverage_from_path(path_mask, free_mask, radius, p0=1.0):
    distance = distance_transform_edt(~path_mask)
    probability = p0 * np.exp(-distance / radius)
    probability[~free_mask] = np.nan
    return probability

這仍假設單次 closest approach；如要表達重複經過，應累積每次 detection attempt。

七、原結果如何解讀

舊模擬報告：

binary coverage 約 32%；
mean coverage intensity 0.188；
median 0；
四象限約 30.7%–33.1%。

這些數值與「螺旋不留空白」互相矛盾；median 0 表示至少一半 grid 沒有得到正 coverage。原因包括圈距過大、外圈越界與障礙物周圍斷裂。

四象限差異小只說明以地圖中心為起點的幾何大致對稱，不能證明螺旋優於 lawnmower。累積距離對時間呈直線，亦只是因程式把 walking speed 設為常數：

t=L/v

的直接結果，並非效率驗證。

八、Monte Carlo 實驗

若失物位置未知，可直接抽樣 $X^{(b)}\sim\pi$ ：

def evaluate_path(path, object_samples, detector, max_time):
    found = []
    detection_times = []
    for obj in object_samples:
        result = detector(path, obj, max_time)
        found.append(result.found)
        detection_times.append(result.time if result.found else np.nan)
    return {
        "find_probability": np.mean(found),
        "median_time_if_found": np.nanmedian(detection_times),
    }

實驗因素可包括：

prior：uniform、中心 Gaussian、沿最近活動路線；
detection radius：1、2、4 呎；
effective speed；
obstacle layout；
path family；
location uncertainty；
fatigue：速度或 detection probability 隨時間下降。

每個情景比較 $P_{\rm find}$ 、expected time to detection、path length、 minimum clearance 和未覆蓋概率質量。

九、多人搜尋

多名搜尋者的目標是減少重疊並保持通訊。可把區域按 prior mass 和 travel cost 分區，或解 multi-agent coverage：

\max_{\gamma_1,\ldots,\gamma_q} \int_{\Omega_f} \pi(x) \left[ 1-\prod_{\ell=1}^{q} \left(1-P_{\rm det}(x\mid\gamma_\ell)\right) \right]dx.

障礙物、互相阻擋與 rendezvous constraint 亦可加入。在 search-and-rescue 情境，安全 protocol、最後已知位置與專業搜索理論遠比固定螺旋重要；本文不能作現場操作指引。

十、互動例子的參數

一個有用的互動工具應讓讀者調整：

prior 中心與擴散；
$R_{\rm eff}$ ；
path spacing；
搜尋速度與時間；
障礙物；
螺旋、lawnmower、probability-greedy 三種路徑。

畫面應同時顯示：

黑色 path 與障礙物；
probability-of-detection heatmap；
累積 prior mass searched；
path length 和預計時間；
漏搜區域，而不只是一個「效率百分比」。

結論

Archimedean 螺旋的真正優勢是連續、平滑，並可由中心按先驗概率向外搜尋；它不是在所有地圖上自然最優。圈距必須由有效感測寬度推導，越界與障礙物要用連續 detour 處理，步速亦要按實際偵測任務校準。

原 32% coverage 結果反而提供有用診斷：固定 $a=2$ 的螺旋漏帶嚴重。將目標改為 expected probability of detection，再與 lawnmower 和 probability-guided baseline 比較，才可以回答「在兩小時內怎樣找最有效」。

參考資料

Koopman, B. O. (1980). Search and Screening: General Principles with Historical Applications. Pergamon.
Stone, L. D. (1975). Theory of Optimal Search. Academic Press.
Choset, H. (2001). Coverage for robotics—A survey of recent results. Annals of Mathematics and Artificial Intelligence, 31, 113–126.
Galceran, E., & Carreras, M. (2013). A survey on coverage path planning for robotics. Robotics and Autonomous Systems, 61(12), 1258–1276.