論文の概要: Lifted Disjoint Paths with Application in Multiple Object Tracking
- arxiv url: http://arxiv.org/abs/2006.14550v1
- Date: Thu, 25 Jun 2020 16:49:08 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-17 04:23:21.166534
- Title: Lifted Disjoint Paths with Application in Multiple Object Tracking
- Title（参考訳）: 複数物体追跡における解離経路の応用
- Authors: Andrea Hornakova, Roberto Henschel, Bodo Rosenhahn, Paul Swoboda
- Abstract要約: この問題は整数多成分流と3-SATの低減によってNPハードであることが示される。
高品質なLP-レラクセーションを生成する線形不等式をいくつか提案する。
昇降経路トラッカーは入力検出に関してほぼ最適に割り振られる。
- 参考スコア（独自算出の注目度）: 39.205794818196395
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present an extension to the disjoint paths problem in which additional
\emph{lifted} edges are introduced to provide path connectivity priors. We call
the resulting optimization problem the lifted disjoint paths problem. We show
that this problem is NP-hard by reduction from integer multicommodity flow and
3-SAT. To enable practical global optimization, we propose several classes of
linear inequalities that produce a high-quality LP-relaxation. Additionally, we
propose efficient cutting plane algorithms for separating the proposed linear
inequalities. The lifted disjoint path problem is a natural model for multiple
object tracking and allows an elegant mathematical formulation for long range
temporal interactions. Lifted edges help to prevent id switches and to
re-identify persons. Our lifted disjoint paths tracker achieves nearly optimal
assignments with respect to input detections. As a consequence, it leads on all
three main benchmarks of the MOT challenge, improving significantly over
state-of-the-art.
- Abstract（参考訳）: 本稿では, 経路接続先を提供するために, 追加の \emph{lifted} エッジを導入する不連結経路問題の拡張を提案する。
結果として生じる最適化問題を解き放たれた経路問題と呼ぶ。
この問題は整数多商品フローと3-SATの削減によってNPハードであることが示される。
実用的大域的最適化を実現するために,高品質なlpリラクシエーションを実現する線形不等式を複数提案する。
さらに,提案する線形不等式を分離する効率的な切断平面アルゴリズムを提案する。
lifted disjoint path problem は、複数の対象追跡のための自然なモデルであり、長距離時間相互作用に対するエレガントな数学的定式化を可能にする。
リフテッドエッジは、idスイッチの防止と、人物の再識別に役立つ。
移動経路追跡装置は入力検出に関してほぼ最適な割り当てを実現する。
その結果、MOTチャレンジの3つの主要なベンチマークすべてに導かれ、最先端よりも大幅に改善されている。
関連論文リスト
- Pathwise optimization for bridge-type estimators and its applications [49.1574468325115]
パスワイズ法は、ペナライズされた推定器の完全な経路を効率的に計算することができる。
これらのアルゴリズムを離散時間で観測されたプロセスのペナル化推定に適用する。
論文 参考訳（メタデータ） (2024-12-05T10:38:29Z) - Flow Priors for Linear Inverse Problems via Iterative Corrupted Trajectory Matching [35.77769905072651]
本稿では,MAP推定器を効率的に近似する反復アルゴリズムを提案し,様々な線形逆問題の解法を提案する。
本アルゴリズムは,MAPの目的を局所MAP'の目的の和で近似できるという観測によって数学的に正当化される。
我々は,超解法,デブロアリング,インペイント,圧縮センシングなど,様々な線形逆問題に対するアプローチを検証する。
論文 参考訳（メタデータ） (2024-05-29T06:56:12Z) - Optimal and Bounded Suboptimal Any-Angle Multi-agent Pathfinding [13.296796764344169]
提案手法は,最初の最適非角度マルチエージェントパスフィンディングアルゴリズムである。
我々のプランナーは、Continuous Conflict-based Search (CCBS)アルゴリズムと、Safe Interval Path Planning (TO-AA-SIPP)の最適な任意の角度変種に基づいている。
古典的MAPFから任意の角度設定、すなわち Disjoint Splitting と Multi-Constraint への2つの手法を適用する。
論文 参考訳（メタデータ） (2024-04-25T07:41:47Z) - PathFinder: Guided Search over Multi-Step Reasoning Paths [80.56102301441899]
木探索に基づく推論経路生成手法であるPathFinderを提案する。
動的デコードの統合により、多様な分岐とマルチホップ推論を強化する。
我々のモデルは、大きな分岐因子を持つビームサーチに類似した複雑さを反映して、よく、長く、目に見えない推論連鎖を一般化する。
論文 参考訳（メタデータ） (2023-12-08T17:05:47Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳（メタデータ） (2023-10-08T23:39:38Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳（メタデータ） (2023-07-17T20:11:56Z) - Enhanced Multi-Objective A* Using Balanced Binary Search Trees [35.63053398687847]
アルゴリズムのような多目的A* (MOA*) は、そのノードに到達した非支配パスを追跡するために、検索中に任意のノードに「フロンティア」セットを保持する。
バランスの取れた二分探索木を利用して,これらのフロンティアを多目的に効率的に維持する手法を提案する。
論文 参考訳（メタデータ） (2022-02-18T02:54:58Z) - Continuation Path with Linear Convergence Rate [18.405645120971496]
経路追従アルゴリズムは、一連のサブプロブレムを順次解決する合成最適化問題によく用いられる。
本稿では,経路追従アルゴリズムの一次双対解析と,対象問題に対する線形収束率を保証するために,各サブプロブレムがどの程度正確に解けるかを決定する。
スパーシリティ誘導ペナルティによる最適化を考慮し、正規化パラメータに対するアクティブセットの変化を分析する。
論文 参考訳（メタデータ） (2021-12-09T18:42:13Z) - Pairwise Symmetry Reasoning for Multi-Agent Path Finding Search [43.40580211016752]
マルチエージェントパス発見(mapf)は,協調エージェントのチームに対して,衝突のないパスを計画することを求める課題である。
MAPFが解決しにくい理由の1つは、ペアワイズ対称性と呼ばれる現象によるものであることを示しています。
対称性の発生を効率的に検出し、特殊な制約を用いて解決する様々な推論手法を提案します。
論文 参考訳（メタデータ） (2021-03-12T07:27:35Z) - Hybrid Trilinear and Bilinear Programming for Aligning Partially
Overlapping Point Sets [85.71360365315128]
多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。
まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。
次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
論文 参考訳（メタデータ） (2021-01-19T04:24:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。