iSAM
iSAM 將 SLAM 表述為平滑（smoothing）問題並保留整條軌跡，使資訊矩陣維持自然稀疏；相對地，濾波在邊際化位姿時會使資訊矩陣變稠密。方法以增量更新平方根資訊矩陣（QR 分解）的方式，只重算受新量測影響的項目。遇到迴圈造成填充（fill-in）時，採週期性變數重排序並重新分解；另提供由分解因子有效取得邊際協方差的演算法，以支援即時資料關聯。
本頁內容
iSAM performs incremental updates of the square-root information matrix of the smoothing problem, with periodic reordering and relinearization, and efficient covariance recovery for data association.
技術屬性
欄位內容為文獻擷取紀錄的原文用語（英文），以原文為據；「未查證」表示本研究尚未讀到該資訊，不代表該方法不具備此能力。
| 感測輸入 | laser range data (Victoria Park: tree landmarks from a simple tree detector; Intel: pose constraints from scan matching; MIT Killian Court: data preprocessed into pose constraints)、vehicle odometry (Victoria Park) |
|---|---|
| 原文測試平台 | vehicle、simulation |
| 狀態估計 | incremental QR update of the square-root information matrix by Givens rotations (new rows eliminated, new variables appended); periodic block COLAMD variable reordering followed by full refactorization every 100 steps (every 20 steps for the Intel dataset); relinearization performed only at these reordering steps; OCaml implementation with automatic differentiation |
| 資料關聯 | maximum likelihood data association: Mahalanobis-distance cost matrix solved as a minimum-cost assignment by the Jonker-Volgenant-Castanon algorithm, using marginal covariances recovered from the square-root factor either exactly (dynamic programming over non-zeros of R) or conservatively (initial landmark uncertainty); nearest neighbour evaluated for comparison; pose-only experiments assume known correspondences |
| 時間表示 | discrete poses |
| 去畸變 | 不適用 |
| 迴圈閉合 | handles loops in the trajectory; fill-in controlled by periodic reordering |
| 全域最佳化 | full trajectory and map smoothing (exact solution of the linearized problem) |
| 地圖表示 | landmarks or pose-only graph |
| 先驗資訊 | none |
| 可輸出幾何 | full trajectory and landmark map with access to marginal covariances (Victoria Park map has 140 distinct landmarks); for Intel and Killian Court the figures show the final trajectory with an evidence grid map (Figs. 10b, 11b) |
| 計算需求 | real-time on 2 GHz Pentium M laptop in OCaml implementation (Sec. VI) |
使用設備
原文使用的感測器、運算硬體與載具（equipment）。型號保留原文寫法，連結到設備頁中同一型號的歸併名稱；角色依原文用途分為方法輸入、資料集感測器、執行運算平台、參考或真值量測（reference or ground truth）與比較對象設備。
| 類別 | 型號（原文寫法） | 角色 | 資料集 | 原文規格 | 出處 |
|---|---|---|---|---|---|
| LiDAR | laser range sensor (model not stated) | 資料集感測器 | Sydney Victoria Park | laser-range data; 3640 tree landmark measurements extracted | (Kaess et al., 2008, Sec. VI-A) |
| LiDAR | laser range sensor (model not stated) | 資料集感測器 | Intel dataset | laser range data preprocessed by scan matching into 910 poses and 4453 constraints | (Kaess et al., 2008, Sec. VI-B) |
| LiDAR | laser range sensor (model not stated) | 資料集感測器 | MIT Killian Court | laser range data preprocessed into 1941 poses and 2190 pose constraints | (Kaess et al., 2008, Sec. VI-B) |
| GNSS 接收器 | Differential GPS (receiver not stated) | 參考或真值量測 | Sydney Victoria Park | shown in Fig. 8 only for visual comparison; not used to obtain the results; unavailable in many places | (Kaess et al., 2008, Fig. 8 caption) |
| 輪式或腿式里程計 | vehicle odometry (sensor not stated) | 資料集感測器 | Sydney Victoria Park | 原文未報告 | (Kaess et al., 2008, Sec. VI-A) |
| 運算硬體 | Pentium M | 執行運算平台 | 未標示 | 2 GHz; laptop computer; timings of the OCaml implementation | (Kaess et al., 2008, Sec. VI) |
作者報告的優勢與限制
優勢
- Exact yet efficient solution of the linearized smoothing problem with access to marginal covariances (abstract; Sec. VIII)
- Constant number of Givens rotations per step in pure exploration (Sec. III-C, Fig. 4)
- Periodic reordering keeps the factor sparse on trajectories with many loops; one to three orders of magnitude faster than purely incremental or batch solutions in the 8-loop simulation (Sec. IV-A, Fig. 5)
- Victoria Park with unknown data association solved in 464 s versus 26 min of recording, over 3 times faster than real time; final factor has 9.79 entries per column (Sec. VI-A)
- On Manhattan the normalized chi-square after one extra relinearization equals the full nonlinear optimum (1.0375) (Sec. VI-B)
限制
- Requires periodic batch steps for variable reordering and relinearization, as stated by the follow-up iSAM2 paper (Kaess et al., 2012, Conclusion)
- Authors list incremental variable ordering and incremental relinearization as open improvements (Sec. VIII)
- Exact marginal covariance recovery becomes expensive in large environments and cannot be run every step; conservative estimates are used online (Sec. V-E)
- Fill-in grows markedly on the Intel dataset (coarse run then detailed exploration with many redundant constraints), requiring a shorter reordering interval (Sec. VI-C, Fig. 12)
營建工程相關證據
未在營建場域驗證。真實資料為公園（Victoria Park）、建物內（Intel）與 MIT Killian Court 的雷射資料集，只評估計算時間與平方根因子稀疏度；正規化 χ2 只用於模擬的 Manhattan 資料集，並未評估點雲或地圖幾何精度（Sec. VI）。結論僅提及未來可用於建物或城市尺度的即時建圖（Sec. VIII）。
原文驗證環境：模擬、公開基準、已完工建築
報告的性能數據
以下是原文作者報告的性能數值（author-reported results），不是本研究重新量測的結果。每張圖只並列同一個比較組（comparison group，同一張表、同一組實驗設定）內的方法；不同比較組之間的數值不可直接比較，也不構成排名。
本方法共出現在 7 個比較組，合計 70 筆紀錄。以下列出本方法紀錄最多的 4 組，其餘 3 組列在最後，並連到性能比較頁。
Kaess et al., 2012 · Table 1 本方法 36 筆
表格設定（擷取紀錄原文）：Runtime comparison (iSAM1 and HOG-Man set to solve in every step, SPA with standard parameters, iSAM2 relinearizing every 10 steps); per-step average, standard deviation and maximum in ms and overall time in s (P poses, M measurements, L landmarks); P 20000, M 26770, simulated 2D pose graph (Kaess et al., 2012, Table 1)
average time per step，City20000 · full sequence
只並列這張表在相同設定下報告的方法；以「本方法：」開頭者為本頁方法。失敗、未執行與未報告以標記呈現，不是 0。
按 Tab 進入圖表後，用上下方向鍵逐一瀏覽各類別，Esc 關閉提示框；也可開啟表格檢視閱讀全部數值。
這些是 Kaess et al., 2012 在此表設定下報告的數值（author-reported results），只能在同一個比較組內對照，不代表方法在其他資料或設定下的表現。
資料來源作者報告值(Kaess et al., 2012, Table 1)
| 方法（原文寫法） | 報告值 | 出處 |
|---|---|---|
| iSAM2原文提出硬體：laptop with Intel 1.6 GHz i7-720; iSAM2 single-threaded research C++ (alpha 0.001, beta 0.1, relinearization every 10 steps); iSAM1 v1.6 standard parameters; HOG-Man svn rev 14 with -update 1; SPA from ROS svn rev 36438 | 16.1 ms | (Kaess et al., 2012, Table 1) |
| iSAM1本方法硬體：laptop with Intel 1.6 GHz i7-720; iSAM2 single-threaded research C++ (alpha 0.001, beta 0.1, relinearization every 10 steps); iSAM1 v1.6 standard parameters; HOG-Man svn rev 14 with -update 1; SPA from ROS svn rev 36438 | 7.05 ms | (Kaess et al., 2012, Table 1) |
| HOG-Man硬體：laptop with Intel 1.6 GHz i7-720; iSAM2 single-threaded research C++ (alpha 0.001, beta 0.1, relinearization every 10 steps); iSAM1 v1.6 standard parameters; HOG-Man svn rev 14 with -update 1; SPA from ROS svn rev 36438 | 27.4 ms | (Kaess et al., 2012, Table 1) |
| SPA硬體：laptop with Intel 1.6 GHz i7-720; iSAM2 single-threaded research C++ (alpha 0.001, beta 0.1, relinearization every 10 steps); iSAM1 v1.6 standard parameters; HOG-Man svn rev 14 with -update 1; SPA from ROS svn rev 36438 | 48.7 ms | (Kaess et al., 2012, Table 1) |
Kaess et al., 2008 · Table I 本方法 12 筆
資料集與序列simulated loop (500 poses, 240 landmarks) · full run
表格設定（擷取紀錄原文）：Simulated loop with 500 poses and 240 landmarks, significant measurement noise, 3% of measurements replaced by random ones; times include factor update, solving for all variables and the data association step, for every step (Kaess et al., 2008, Table I)
overall execution time，simulated loop (500 poses, 240 landmarks) · full run
只並列這張表在相同設定下報告的方法；以「本方法：」開頭者為本頁方法。失敗、未執行與未報告以標記呈現，不是 0。
按 Tab 進入圖表後，用上下方向鍵逐一瀏覽各類別，Esc 關閉提示框；也可開啟表格檢視閱讀全部數值。
這些是 Kaess et al., 2008 在此表設定下報告的數值（author-reported results），只能在同一個比較組內對照，不代表方法在其他資料或設定下的表現。
資料來源作者報告值(Kaess et al., 2008, Table I)
| 方法（原文寫法） | 報告值 | 出處 |
|---|---|---|
| NN本方法硬體：not stated for this experiment (Sec. VI names a 2 GHz Pentium M laptop only for the Sec. VI timings); OCaml implementation | 2.03 s | (Kaess et al., 2008, Table I) |
| ML conservative本方法原文提出硬體：not stated for this experiment (Sec. VI names a 2 GHz Pentium M laptop only for the Sec. VI timings); OCaml implementation | 2.8 s | (Kaess et al., 2008, Table I) |
| ML exact, efficient本方法原文提出硬體：not stated for this experiment (Sec. VI names a 2 GHz Pentium M laptop only for the Sec. VI timings); OCaml implementation | 27.5 s | (Kaess et al., 2008, Table I) |
| ML exact, full本方法硬體：not stated for this experiment (Sec. VI names a 2 GHz Pentium M laptop only for the Sec. VI timings); OCaml implementation | 429 s | (Kaess et al., 2008, Table I) |
Kaess et al., 2008 · Text Sec.VI-B timing 本方法 9 筆
表格設定（擷取紀錄原文）：Pose-only iSAM with known data association, full solution after each step; 3500 poses, 5598 constraints; reordering and relinearization every 100 steps (Kaess et al., 2008, Text Sec.VI-B timing)
total computation time，Manhattan world (Olson et al.) · full sequence
這張表在此指標與資料序列只列出本方法一筆，沒有可並列的其他方法，因此不畫圖，數值與出處見下表。這是 Kaess et al., 2008 在此表設定下報告的數值（author-reported results），不代表方法在其他資料或設定下的表現。
| 方法（原文寫法） | 報告值 | 出處 |
|---|---|---|
| iSAM本方法原文提出硬體：2 GHz Pentium M laptop; OCaml implementation | 140.9 s | (Kaess et al., 2008, Sec. VI-B) |
Kaess et al., 2008 · Text Sec.VI-A 本方法 6 筆
資料集與序列Victoria Park · full sequence
表格設定（擷取紀錄原文）：Sydney Victoria Park: 6969 of 7247 frames retained, 3640 landmark measurements from a tree detector, 4 km, 26 min recording; unknown correspondences use ML data association with conservative estimates (Kaess et al., 2008, Text Sec.VI-A)
total time, unknown correspondences, solving after every frame，Victoria Park · full sequence
這張表在此指標與資料序列只列出本方法一筆，沒有可並列的其他方法，因此不畫圖，數值與出處見下表。這是 Kaess et al., 2008 在此表設定下報告的數值（author-reported results），不代表方法在其他資料或設定下的表現。
| 方法（原文寫法） | 報告值 | 出處 |
|---|---|---|
| iSAM本方法原文提出硬體：2 GHz Pentium M laptop; OCaml implementation | 464 s | (Kaess et al., 2008, Sec. VI-A) |
其他比較組
來源
Kaess et al., 2008
（2008）iSAM: Incremental Smoothing and MappingIEEE Transactions on Robotics, 24(6):1365-1378
同儕審查已出版已讀全文經典查證後修正