Karto SLAM (Sparse Pose Adjustment)
本文提出稀疏位姿調整（Sparse Pose Adjustment, SPA），以 Levenberg-Marquardt 最佳化 2D 位姿圖。作者以有序資料結構一次走訪全部約束即建出稀疏的 H 矩陣，再用 CSparse 的稀疏 Cholesky 分解直接求解線性子問題；每條約束保留完整的精度矩陣，因此能處理非球形的共變異。增量模式採用可接續的 LM，保留上一輪的 lambda，每加入一個節點只做一次迭代。實驗用的位姿圖由 SRI 的 Karto 以相關式掃描匹配產生，包含序列匹配與迴圈閉合約束；SPA 本身只是後端，不處理資料關聯。
本頁內容
Sparse Levenberg-Marquardt back end for 2D pose graphs that builds the sparse system in one ordered pass and solves it by sparse direct Cholesky, used as the optimizer behind the Karto laser SLAM front end.
技術屬性
欄位內容為文獻擷取紀錄的原文用語（英文），以原文為據；「未查證」表示本研究尚未讀到該資訊，不代表該方法不具備此能力。
| 感測輸入 | front-end agnostic optimizer; test graphs were built by the Karto front end from 2D laser logs (laser model not reported) |
|---|---|
| 原文測試平台 | 原文未報告 (63 stored indoor robot logs; platforms not described)、simulation |
| 狀態估計 | Levenberg-Marquardt nonlinear least squares on a 2D pose graph with full precision matrices per constraint; the linear subproblem is built in one ordered pass (per-column std::map blocks converted to compressed column storage) and solved by sparse direct Cholesky (CSparse with AMD ordering); a 'continuable LM' keeps lambda between incremental iterations (Sec. IV.B-F; Tables I-II) |
| 資料關聯 | 不適用 to SPA itself; constraints and covariances come from the Karto front end, which uses the correlation method of Konolige and Chou (extended by Olson) for sequential matching and for loop-closure matching of sets of scans (Sec. V) |
| 時間表示 | discrete poses |
| 去畸變 | 不適用 |
| 迴圈閉合 | 不適用 to the optimizer; loop-closure constraints are produced by Karto's scan-set matching (Sec. V) |
| 全域最佳化 | batch or incremental LM optimization of the whole 2D pose graph; spanning-tree initialization gave the best results and was needed for global convergence on the large synthetic graph (Sec. VI.B, VI.D) |
| 地圖表示 | 2D pose graph (in Karto, poses carry laser scans); SPA holds no map of its own |
| 先驗資訊 | none (initialization from odometry or from a spanning tree of the graph) |
| 可輸出幾何 | optimized 2D poses (x, y, theta); maps are rendered from scans at the optimized poses (Fig. 3) |
| 計算需求 | Intel Core i7-920 at 2.67 GHz: 150 ms to fully optimize the 3603-node MIT map from odometry, less than 15 ms per node in incremental mode (Sec. I); about 10 s for the 100k-node, 400k-constraint synthetic graph from spanning-tree initialization (Fig. 6) |
使用設備
原文使用的感測器、運算硬體與載具（equipment）。型號保留原文寫法，連結到設備頁中同一型號的歸併名稱；角色依原文用途分為方法輸入、資料集感測器、執行運算平台、參考或真值量測（reference or ground truth）與比較對象設備。
| 類別 | 型號（原文寫法） | 角色 | 資料集 | 原文規格 | 出處 |
|---|---|---|---|---|---|
| 運算硬體 | Intel Core i7-920 | 執行運算平台 | 未標示 | 2.67 GHz | (Konolige et al., 2010, Sec. VI) |
作者報告的優勢與限制
優勢
- In batch mode SPA and PCG converged to almost the same error, both with more than 10 times lower error than TORO on the larger graphs, and SPA needed almost an order of magnitude less computation than PCG or TORO for almost all graphs (Sec. VI.B).
- Full optimization of the 3603-node, 4986-constraint MIT map from odometry took 150 ms; incremental mode needed less than 15 ms per node addition (Sec. I; Fig. 1).
- On the 100k-node synthetic graph, on-line SPA reached the same minimum chi-square as TreeMap while TreeMap used up to 100 s per iteration (Sec. VI.D; Fig. 8).
- As a pose-graph method SPA allows incremental additions and deletions, which the authors link to lifelong mapping (Sec. VII).
限制
- With all nodes initialized at (0,0,0), SPA and PCG converged to non-global minima on all real datasets, while TORO recovered the correct topology (Sec. VI.B).
- On the synthetic graph SPA did not converge to the global minimum from odometry or zero initialization; spanning-tree initialization was required (Sec. VI.D).
- The 63 indoor datasets have no ground truth; accuracy is the covariance-weighted chi-square error of the constraints, which reflects scan alignment only if the scan matcher is accurate (Sec. VI.A).
- Evaluated only for 2D poses, although the authors state SPA can be parameterized with 3D poses (Sec. I).
- The authors state that none of the real-world datasets they found were challenging for SPA (Sec. VI.C; Sec. VII).
營建工程相關證據
未在營建場域驗證；63 組真實資料都是室內機器人記錄，沒有獨立參考量測。作者指出 100 m 乘 100 m 辦公空間的 2D 雷射地圖可達數千個節點，且位姿圖可增刪節點以支援長期建圖（Sec. I、VII），這與大型建築室內 2D 平面地圖的建立與更新有關（推論）。其 ROS 實作 slam_karto 以及後續的 SLAM Toolbox （Macenski & Jambrecic, 2021）都以 Karto 為基礎，是室內 2D 雷射建圖的現成工具（推論）。
原文驗證環境：已完工建築、模擬
報告的性能數據
以下是原文作者報告的性能數值（author-reported results），不是本研究重新量測的結果。每張圖只並列同一個比較組（comparison group，同一張表、同一組實驗設定）內的方法；不同比較組之間的數值不可直接比較，也不構成排名。
本方法共出現在 1 個比較組，合計 4 筆紀錄。
Konolige et al., 2010 · Text Sec. I, VI, VII 本方法 4 筆
資料集與序列Karto-generated pose graph of the MIT corridor log · MIT corridor map (3603 nodes, 4986 constraints)
表格設定（擷取紀錄原文）：Full nonlinear optimization of the MIT corridor graph from odometry initialization (Konolige et al., 2010, Text Sec. I, VI, VII)
time for full nonlinear optimization of the graph，Karto-generated pose graph of the MIT corridor log · MIT corridor map (3603 nodes, 4986 constraints)
這張表在此指標與資料序列只列出本方法一筆，沒有可並列的其他方法，因此不畫圖，數值與出處見下表。這是 Konolige et al., 2010 在此表設定下報告的數值（author-reported results），不代表方法在其他資料或設定下的表現。
| 方法（原文寫法） | 報告值 | 出處 |
|---|---|---|
| SPA本方法原文提出硬體：Intel Core i7-920, 2.67 GHz | 0.15 s | (Konolige et al., 2010, Sec. I; Fig. 1) |
來源
Konolige et al., 2010
（2010）Efficient Sparse Pose Adjustment for 2D mapping2010 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2010), Taipei, Taiwan, pp. 22-29
DOI 10.1109/iros.2010.5649043程式碼
同儕審查已出版已讀全文經典查證後修正
相關版本
- 程式碼釋出：SPA code and datasets page stated in the paper (www.ros.org/research/2010/spa; HTTP 301 to https, content not checked) https://www.ros.org/research/2010/spa
- 程式碼釋出：ros-perception/sparse_bundle_adjustment (contains spa2d.h, BSD) https://github.com/ros-perception/sparse_bundle_adjustment
- software using this method：ros-perception/slam_karto ROS wrapper whose SpaSolver is built on spa2d.h with the open_karto front end (LGPL) https://github.com/ros-perception/slam_karto
- derived software：SLAM Toolbox builds on Open Karto and replaced its Sparse Bundle Adjustment interface with Ceres (Macenski & Jambrecic, 2021, Features) https://doi.org/10.21105/joss.02783
程式碼：https://github.com/ros-perception/sparse_bundle_adjustment（授權：BSD (spa2d.h header and package.xml); the ROS slam_karto wrapper that uses it is LGPL (package.xml; spa_solver.h header LGPL-3.0-or-later) and open_karto is LGPLv3 (package.xml)）。有公開程式碼不等於已被重現，也不代表目前版本與論文版本相同。