DP-SLAM
DP-SLAM 以粒子濾波同時追蹤機器人位姿與地圖假設，不需預先指定地標。為避免每個粒子複製整張地圖，作者提出分散式粒子建圖（DP-mapping）：全系統只保留一張佔據網格，每格以平衡樹記錄曾更新該格的粒子 ID，並維護經修剪與合併的最小粒子祖先樹；粒子查詢某格時，沿祖先找出最近一次的觀測紀錄。如此可同時維持數千張候選地圖，並在沒有明確迴圈閉合步驟下閉合約 60 m 的迴圈。
本頁內容
Laser-only particle filter over poses and maps that shares one occupancy grid among particles through an ancestry tree and per-cell balanced trees (DP-mapping), keeping thousands of map hypotheses and closing loops without explicit loop closing.
技術屬性
欄位內容為文獻擷取紀錄的原文用語（英文），以原文為據；「未查證」表示本研究尚未讀到該資訊，不代表該方法不具備此能力。
| 感測輸入 | 2D laser range finder (SICK)、wheel odometry (shaft encoders) |
|---|---|
| 原文測試平台 | wheeled UGV (iRobot ATRV Jr., skid steering) |
| 狀態估計 | particle filter over robot poses and maps with a calibrated odometry motion model; particle culling evaluates the posterior in k passes over disjoint subsets of laser readings and drops poor particles early (Sec. 2, 4) |
| 資料關聯 | ray tracing each laser cast through the particle's map to the first obstruction; Gaussian discrepancy with 5 cm standard deviation (Sec. 2.1) |
| 時間表示 | discrete poses (new observation after about 20 cm of motion) |
| 去畸變 | 原文未報告 |
| 迴圈閉合 | implicit through maintaining multiple map hypotheses; no explicit loop-closing step or environment assumption (Sec. 4) |
| 全域最佳化 | none |
| 地圖表示 | single binary occupancy grid (3 cm cells) in which each cell stores a balanced tree keyed by the IDs of particles that updated it, plus a pruned and collapsed minimal particle ancestry tree (Sec. 3.2; Sec. 4) |
| 先驗資訊 | none |
| 可輸出幾何 | 2D occupancy grid (cross-section at the 7 cm laser height) |
| 計算需求 | 2.4 GHz Pentium 4: run time close to data-collection time; culling with k = 6 gave about a 6x speed-up; worst-case cost O(ADP lg P) per sweep (Sec. 3.3-3.4; Sec. 4) |
使用設備
原文使用的感測器、運算硬體與載具（equipment）。型號保留原文寫法，連結到設備頁中同一型號的歸併名稱；角色依原文用途分為方法輸入、資料集感測器、執行運算平台、參考或真值量測（reference or ground truth）與比較對象設備。
| 類別 | 型號（原文寫法） | 角色 | 資料集 | 原文規格 | 出處 |
|---|---|---|---|---|---|
| LiDAR | SICK laser range finder | 方法輸入 | 未標示 | front-mounted 7 cm above the floor; 180 deg at 1 deg spacing; effective range up to 8 m; distance error typically below 5 mm | (Eliazar & Parr, 2003, Sec. 4.1) |
| 載具平台 | iRobot ATRV Jr. | 方法輸入 | 未標示 | skid steering; shaft encoders unreliable when turning | (Eliazar & Parr, 2003, Sec. 4.1) |
| 運算硬體 | 2.4 GHz Pentium 4 | 執行運算平台 | 未標示 | fast PC used for offline processing of the logged data | (Eliazar & Parr, 2003, Sec. 4) |
作者報告的優勢與限制
優勢
- Closed a 60 m loop with 9000 particles and no discernible misalignment, whereas keeping only the best particle's single map produced a considerable misalignment (Sec. 4.2; Figs. 1-2).
- Ancestry trees coalesced as recently as about 20 generations and never beyond 90 in the test domain, keeping storage close to linear in practice (Sec. 4.3).
- Particle culling with k = 6 gave about a 6x speed-up, and run time was close to data-collection time (Sec. 4).
- No assumptions about the environment or the existence of loops (Sec. 4).
限制
- The binary occupancy grid causes discretization errors at object edges and confusion with small objects such as power cords hanging from desks (Sec. 5).
- The laser is treated as deterministic when updating the map but as noisy when localizing (Sec. 5).
- A fixed-height laser gives an incomplete view of the environment (Sec. 5).
- Sparse-data environments may cause premature coalescence unless an excessive number of particles is used (Sec. 4.3).
- Using one in four laser casts required 30,000 particles for good maps (Sec. 4.3).
營建工程相關證據
未在營建場域驗證；測試為 Duke 大學資訊系館二樓約 16 m 乘 14 m 的走廊迴圈，只以地圖目視比較，沒有定量誤差。其保存多張地圖假設、待證據充足再收斂的做法，與營建場域中暫時結構造成量測歧義時的建圖穩健性相關（推論）。
原文驗證環境：已完工建築
報告的性能數據
以下是原文作者報告的性能數值（author-reported results），不是本研究重新量測的結果。每張圖只並列同一個比較組（comparison group，同一張表、同一組實驗設定）內的方法；不同比較組之間的數值不可直接比較，也不構成排名。
本方法共出現在 1 個比較組，合計 5 筆紀錄。
Eliazar & Parr, 2003 · Text Sec. 4 本方法 5 筆
資料集與序列Duke University Computer Science building, 2nd floor (iRobot ATRV Jr., SICK) · hallway loop log
表格設定（擷取紀錄原文）：Hallway loop about 16 m x 14 m, 60 m traveled before re-observing the start; 3 cm grid (Eliazar & Parr, 2003, Text Sec. 4)
number of particles for the map closing the loop with no discernible misalignment，Duke University Computer Science building, 2nd floor (iRobot ATRV Jr., SICK) · hallway loop log
這張表在此指標與資料序列只列出本方法一筆，沒有可並列的其他方法，因此不畫圖，數值與出處見下表。這是 Eliazar & Parr, 2003 在此表設定下報告的數值（author-reported results），不代表方法在其他資料或設定下的表現。
| 方法（原文寫法） | 報告值 | 出處 |
|---|---|---|
| DP-SLAM本方法原文提出硬體：2.4 GHz Pentium 4 | 9000 particles有附註註記（擷取紀錄）：loop closed with no discernible misalignment | (Eliazar & Parr, 2003, Sec. 4.2; Fig. 1) |
來源
Eliazar & Parr, 2003
（2003）DP-SLAM: Fast, Robust Simultaneous Localization and Mapping Without Predetermined LandmarksProceedings of the Eighteenth International Joint Conference on Artificial Intelligence (IJCAI-03), pp. 1135-1142
同儕審查已出版已讀全文經典查證後修正
相關版本
- 程式碼釋出：OpenSLAM DP-SLAM source https://github.com/OpenSLAM-org/openslam_dpslam
- follow up：DP-SLAM 2.0 (listed on the OpenSLAM page; not read) https://openslam-org.github.io/dpslam.html
程式碼：https://github.com/OpenSLAM-org/openslam_dpslam（授權：Duke University research licence stated on the OpenSLAM.org DP-SLAM page (provided without cost and as is, with an indemnification clause); not an OSI-approved licence）。有公開程式碼不等於已被重現，也不代表目前版本與論文版本相同。