iSAM2
本文提出 Bayes tree 資料結構，把稀疏矩陣分解與圖模型推論連結起來，並據此發展 iSAM2。新量測加入時，iSAM2 只移除並重新消去受影響的樹頂部團（clique），再把未受影響的子樹接回；變數排序以約束式 CCOLAMD 增量進行，把最近存取的變數推向樹根。「流動式重線性化」（fluid relinearization）只在變數增量超過門檻 β 時才更新線性化點，部分狀態更新則在解的變化小於門檻 α 時停止回代。因此 iSAM2 不再需要 iSAM 的週期性批次步驟。作者在模擬與真實的 2D 位姿圖、2D 地標資料集及模擬 3D 位姿圖上，與 iSAM1、HOG-Man、SPA 比較每步計算時間與正規化 χ2。
本頁內容
iSAM2 uses the Bayes tree to perform fully incremental nonlinear smoothing with incremental reordering and threshold-based fluid relinearization, eliminating periodic batch steps.
技術屬性
欄位內容為文獻擷取紀錄的原文用語（英文），以原文為據；「未查證」表示本研究尚未讀到該資訊，不代表該方法不具備此能力。
| 感測輸入 | 未記錄 |
|---|---|
| 原文測試平台 | simulation、not described in the paper (real datasets named only: Intel, Killian Court and Victoria Park laser range data) |
| 狀態估計 | incremental Gauss-Newton on a factor graph via the Bayes tree: cliques affected by new factors or by relinearization are removed and re-eliminated (incomplete Cholesky within cliques) and orphaned sub-trees re-attached; incremental constrained COLAMD ordering forces recently accessed variables to the root; fluid relinearization when a variable's delta exceeds beta; partial state update stops back-substitution where changes fall below alpha; exponential-map retraction for 3D rotations |
| 資料關聯 | 不適用 (back-end; data association supplied externally) |
| 時間表示 | discrete poses |
| 去畸變 | 不適用 |
| 迴圈閉合 | 不適用 (processes loop-closure factors provided by the front-end) |
| 全域最佳化 | incremental full smoothing over all variables without periodic batch steps |
| 地圖表示 | pose graph and optional landmarks |
| 先驗資訊 | none |
| 可輸出幾何 | incrementally updated trajectory and landmark estimates |
| 計算需求 | online incremental; single-threaded research C++ implementation (released in gtsam) with alpha = 0.001, beta = 0.1 and relinearization every 10 steps; all timings on a laptop with an Intel 1.6 GHz i7-720 (Table 1) |
使用設備
原文使用的感測器、運算硬體與載具（equipment）。型號保留原文寫法，連結到設備頁中同一型號的歸併名稱；角色依原文用途分為方法輸入、資料集感測器、執行運算平台、參考或真值量測（reference or ground truth）與比較對象設備。
| 類別 | 型號（原文寫法） | 角色 | 資料集 | 原文規格 | 出處 |
|---|---|---|---|---|---|
| LiDAR | laser range sensor (model not stated) | 資料集感測器 | Intel | laser range data converted to a 2D pose graph (910 poses, 4453 measurements) | (Kaess et al., 2012, Fig. 11; Table 1) |
| LiDAR | laser range sensor (model not stated) | 資料集感測器 | Killian Court | laser range data converted to a 2D pose graph (1941 poses, 2190 measurements) | (Kaess et al., 2012, Fig. 11; Table 1) |
| LiDAR | laser range sensor (model not stated) | 資料集感測器 | Victoria Park | laser range data with 151 landmarks, 6969 poses, 10608 measurements | (Kaess et al., 2012, Fig. 12; Table 1) |
| 運算硬體 | Intel i7-720 | 執行運算平台 | 未標示 | 1.6 GHz; laptop; all timing results; iSAM2 research C++ implementation running single-threaded | (Kaess et al., 2012, Comparison to other methods) |
作者報告的優勢與限制
優勢
- Fully incremental reordering and relinearization, no periodic batch steps (abstract; Conclusion)
- Lower average and overall time than SPA on every dataset where SPA was run and similar to iSAM1 overall; its maximum per-step time is still higher than SPA's except on Intel (Timing; Table 1)
- Fastest average time per step on Intel (1.74 ms), Victoria Park (2.34 ms) and Torus10000 (35.2 ms) among the compared methods (Table 1)
- Solution stays very close to the per-step least-squares solution in normalized chi-square, whereas iSAM1 shows larger spikes and HOG-Man consistently larger errors (Accuracy; Fig. 16)
- Fill-in stays close to that of batch ordering thanks to incremental constrained ordering (Fig. 8)
限制
- Update steps are not constant time; large loop closings can become as expensive as a batch solution (Related work)
- Timing spikes follow those of SPA but are almost an order of magnitude higher, partly because no optimized library comparable to CHOLMOD was used (Timing)
- Assumes initialization close enough to the global minimum for convergence, as for any direct solver (Algorithm and complexity)
- Slower than iSAM1 in average time per step on City20000, Manhattan, Killian Court, Trees10000 and Sphere2500, and slower than HOG-Man on W10000 (Table 1)
- (inference from Alg. 5) Relinearization is threshold based, so linearization points of variables whose change stays below beta are not updated
- (inference) Evaluation uses 2D pose graphs, 2D landmark datasets and simulated 3D pose graphs; dense LiDAR mapping workloads are not evaluated in this paper
營建工程相關證據
未在營建場域驗證。實驗為模擬資料集與真實雷射資料集（Intel、Killian Court、Victoria Park）的位姿圖或地標圖，評估每步計算時間、受影響矩陣元素數與正規化 χ2，並未涉及點雲或建物幾何精度（Comparison to other methods）。作者以大型建物多房間建圖說明部分狀態更新的直覺，但沒有對應實驗（Partial state updates）。
原文驗證環境：模擬、公開基準
報告的性能數據
以下是原文作者報告的性能數值（author-reported results），不是本研究重新量測的結果。每張圖只並列同一個比較組（comparison group，同一張表、同一組實驗設定）內的方法；不同比較組之間的數值不可直接比較，也不構成排名。
本方法共出現在 1 個比較組，合計 36 筆紀錄。
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., 2012
（2012）iSAM2: Incremental smoothing and mapping using the Bayes treeThe International Journal of Robotics Research, 31(2):216-235
DOI 10.1177/0278364911430419程式碼
同儕審查已出版已讀全文經典
相關版本
- 會議版：The Bayes Tree: An Algorithmic Foundation for Probabilistic Robot Mapping (WAFR 2010, Springer STAR) 10.1007/978-3-642-17452-0_10
- 會議版：iSAM2: Incremental smoothing and mapping with fluid relinearization and incremental variable reordering (ICRA 2011) 10.1109/icra.2011.5979641
- 程式碼釋出：Source code released as part of the gtsam library (per paper); current repository borglab/gtsam https://github.com/borglab/gtsam
程式碼：https://github.com/borglab/gtsam（授權：BSD (GTSAM LICENSE.BSD)）。有公開程式碼不等於已被重現，也不代表目前版本與論文版本相同。