論文の概要: Class-Based Heuristic Selection for Solving the Flying Block Puzzle
- arxiv url: http://arxiv.org/abs/2608.27476v1
- Date: Thu, 20 Aug 2026 09:18:21 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-06 19:38:41.443029
- Title: Class-Based Heuristic Selection for Solving the Flying Block Puzzle
- Title（参考訳）: 飛行ブロックノズルの解法のためのクラスベースヒューリスティック選択
- Abstract要約: ヒューリスティック検索は、倉庫のロジスティクスからロボットナビゲーションまで、自律システムの計画を立てている。
本研究では,NP完全空間計画マイクロワールドであるFlying Block Puzzleを用いて,この問題について検討する。
クラスベースヒューリスティックA*アルゴリズムを導入し, 一般移動制約を統合し, 最小変位コストを推定する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Heuristic search underlies planning in autonomous systems ranging from warehouse logistics to robotic navigation, yet generic heuristics fail to exploit the structural constraints that govern constrained spatial domains, causing search performance to degrade catastrophically on harder instances. We study this problem through the two-column Flying Block Puzzle, a rigorously NP-complete spatial planning microworld whose bottleneck geometry mirrors clearance-to-size constraints encountered in multi-agent path finding, autonomous vehicle navigation, and block relocation systems. We introduce the Class-Based Heuristic A* (CBHA*) algorithm, which integrates a General Move Constraint to capture minimum displacement costs when vacant units are scarce, a formal kinematic taxonomy partitioning the state space into seven mutually exclusive classes with provably admissible heuristics based on vacancy ratio and goal-piece geometry, and a class-conditional tie-breaking mechanism that dynamically switches between depth-priority and vertical-distance ordering to overcome f-value plateaus. Over 146 benchmark instances, CBHA* achieves a 93.4% success rate against 64% for Depth-Prioritized A*, 39% for Standard A*, and 17% for BFS, while reducing node expansions by 87.98% relative to Standard A* and sustaining an average effective branching factor of approximately 3, demonstrating that class-triggered adaptive heuristics constitute a principled mechanism for efficient spatial planning that generalizes structurally to physical constraint systems.
- Abstract（参考訳）: ヒューリスティック検索は、倉庫のロジスティクスからロボットナビゲーションまで、自律システムにおいて計画されているが、一般的なヒューリスティックは制約された空間領域を支配する構造的制約を活用できず、検索性能はより困難なインスタンスで壊滅的に低下する。
この問題を,NP完全空間計画マイクロワールドであるFlying Block Puzzle(Flying Block Puzzle)という,マルチエージェントパス探索,自律走行航法,ブロック再配置システムにおいて発生するクリアランスからサイズまでの制約を反映した,厳密なNP完全空間計画マイクロワールドを通じて研究する。
本稿では, 空き単位が不足している場合に, 最大変位コストを抑えるための一般移動制約(CBHA*)アルゴリズム, 空き比とゴールピース幾何に基づく許容可能なヒューリスティックスを持つ, 状態空間を7つの排他的クラスに分割する形式的キネマティック分類法, およびF値高原を克服するために, 動的に深み優先順序と垂直距離順序を切り替えるクラス条件付きタイブリング機構を導入する。
146のベンチマークインスタンスでCBHA*は64%、標準A*は39%、BFSは17%に対して93.4%の成功率を実現し、標準A*に対して87.98%のノード拡張を減らし、平均的な有効分岐係数を約3で維持し、クラストリガー適応ヒューリスティックが物理的制約系に構造的に一般化する効率的な空間計画の原則的なメカニズムであることを示した。
関連論文リスト
- Adaptive Error Budget Allocation for Fault-Tolerant Quantum Resource Estimation: A Metaheuristic Approach [0.14323566945483496]
システムレベルのリソース推定は、フォールトトレラントな量子コンピューティングツールチェーンの重要なコンポーネントである。
そこで我々は,Azure Quantum Resource Estor上で,微分自由探索を直接行うトレーニングフリー最適化フレームワークを提案する。
MQTベンチの31ファミリーから2から91キュービットに及ぶ433個の回路上で,本フレームワークの評価を行った。
論文 参考訳（メタデータ） (2026-08-16T07:14:29Z) - LocalNav: Distilling Frontier VLMs and Embodied RL for On-Device Object Goal Navigation [53.88286427894783]
視覚言語モデル(VLM)は、ロボット分野において、言語コンテキストによる環境認識を可能にする強力なツールとして登場した。
しかし、彼らの計算フットプリントは、通常、それらをクラウド実行に制限し、リソースに制約のあるロボットへのローカルなデプロイによる低レイテンシの推論を妨げる。
本稿では,大規模フロンティアモデルからの複雑な空間意味推論を,組み込みGPUデバイス上でエッジ実行を行うための軽量な4BパラメータローカルVLMに転送する蒸留戦略を提案する。
論文 参考訳（メタデータ） (2026-06-26T09:11:59Z) - Learning Reactive Dexterous Grasping via Hierarchical Task-Space RL Planning and Joint-Space QP Control [50.28263951510334]
本稿では,リアクティブなデクスタリーグルーピングのためのハイブリッド階層型制御フレームワークを提案する。
提案手法は,低レベル共同実行から高レベル空間意図を明示的に分離する。
我々は厳密なシミュレーションと現実のパイプラインを通して提案したフレームワークを広範囲に検証する。
論文 参考訳（メタデータ） (2026-05-05T04:49:38Z) - O-ConNet: Geometry-Aware End-to-End Inference of Over-Constrained Spatial Mechanisms [6.353145241135741]
O-ConNetは、わずか3つの到達可能なポイントから構造パラメータを推論するエンドツーエンドのフレームワークである。
O-ConNetは、自己構築されたBennett 4Rデータセット上で、Param-MAE 0.276 +/- 0.077とTraj-MAE 0.145 +/- 0.018を達成する。
これらの結果から,エンド・ツー・エンド・ラーニングは閉ループ構造を捕捉し,空間的過拘束機構の逆設計のための実践的経路を提供する可能性が示唆された。
論文 参考訳（メタデータ） (2026-04-02T13:43:53Z) - Adaptive-Horizon Conflict-Based Search for Closed-Loop Multi-Agent Path Finding [10.628717510399046]
MAPFは、倉庫や物流の自動化において、大規模なロボット群の中核的な調整問題である。
既存のアプローチは、固定軌道を生成するオープンループプランナか、信頼性の高い性能保証のないクローズループである。
本稿では,CBSの有限水平変速器をベースとした閉ループであるACCBSについて述べる。
論文 参考訳（メタデータ） (2026-02-12T14:55:16Z) - Resolving Primitive-Sharing Ambiguity in Long-Tailed Industrial Point Cloud Segmentation via Spatial Context Constraints [9.6402526621774]
リデューサやバルブなどの安全クリティカルなコンポーネントは、体系的に誤って分類される。
この研究は、工業用3Dデータに特有の2つの危機を、極端に不均衡な215:1比で特定する。
本研究では,局所的な類似構造を曖昧にするために,近傍の予測整合性を利用する空間的文脈制約を提案する。
論文 参考訳（メタデータ） (2026-01-27T02:52:28Z) - QoS-Aware Hierarchical Reinforcement Learning for Joint Link Selection and Trajectory Optimization in SAGIN-Supported UAV Mobility Management [52.15690855486153]
宇宙空間統合ネットワーク (SAGIN) がユビキタスUAV接続を実現するための重要なアーキテクチャとして登場した。
本稿では,SAGINにおけるUAVモビリティ管理を制約付き多目的関節最適化問題として定式化する。
論文 参考訳（メタデータ） (2025-12-17T06:22:46Z) - CAHC:A General Conflict-Aware Heuristic Caching Framework for Multi-Agent Path Finding [0.0]
我々は、状態と関連する制約コンテキストの両方に基づいて値をキャッシュする一般的なフレームワークであるtextbfCAHC(Conflict-Aware Heuristic Caching)を提案する。
カーライクロボットにおけるCL-CBSのケーススタディを通じてCAHCを実演し、コンフリクト対応キャッシングと適応ハイブリッドを併用したtextbfCARCHASE(Car-like Robot Conflict-Aware Heuristic Adaptive Search Enhancement)を提案する。
キーとなるイノベーションは、(1)制約が状態のコンテキストに影響を及ぼすことを効率的にエンコードするコンパクトなEmphconflict指紋、(2)ドメイン適応型指紋である。
論文 参考訳（メタデータ） (2025-12-13T08:42:18Z) - Towards a Science of Scaling Agent Systems [79.64446272302287]
エージェント評価の定義を定式化し,エージェント量,コーディネーション構造,モデル,タスク特性の相互作用として,スケーリング法則を特徴付ける。
協調指標を用いて予測モデルを導出し,R2=0をクロスバリデーションし,未知のタスク領域の予測を可能にする。
ツールコーディネーショントレードオフ: 固定的な計算予算の下では, ツールヘビータスクはマルチエージェントのオーバーヘッドから不均衡に悩まされ, 2) 能力飽和: 調整が減少または負のリターンを, 単一エージェントのベースラインが45%を超えると達成できる。
論文 参考訳（メタデータ） (2025-12-09T06:52:21Z) - Hierarchical Budget Policy Optimization for Adaptive Reasoning [49.621779447691665]
階層的予算政策最適化(Hierarchical Budget Policy Optimization, HBPO)は、モデルが問題固有の推論深度を犠牲にすることなく学習できる強化学習フレームワークである。
HBPOは、探索空間を予算制約付き階層(512-2560トークン)に分割する。
大規模な実験により、HBPOは平均トークン使用量を最大60.6%削減し、4つの推論ベンチマークで精度を3.14%改善した。
論文 参考訳（メタデータ） (2025-07-21T17:52:34Z) - TransPath: Learning Heuristics For Grid-Based Pathfinding via
Transformers [64.88759709443819]
探索の効率を顕著に向上させると考えられる,インスタンス依存のプロキシを学習することを提案する。
私たちが最初に学ぶことを提案するプロキシは、補正係数、すなわち、インスタンスに依存しないコスト・ツー・ゴの見積もりと完璧な見積もりの比率である。
第2のプロキシはパス確率であり、グリッドセルが最も短いパスに横たわっている可能性を示している。
論文 参考訳（メタデータ） (2022-12-22T14:26:11Z) - Tailored Learning-Based Scheduling for Kubernetes-Oriented Edge-Cloud
System [54.588242387136376]
エッジクラウドシステムのための学習ベースのスケジューリングフレームワークkaisを紹介する。
まず,分散した要求ディスパッチに対応するために,協調型マルチエージェントアクタ-クリティックアルゴリズムを設計する。
次に,多種多様なシステムスケールと構造について,グラフニューラルネットワークを用いてシステム状態情報を埋め込む。
第3に、リクエストディスパッチとサービスオーケストレーションを調和させる2段階のスケジューリングメカニズムを採用します。
論文 参考訳（メタデータ） (2021-01-17T03:45:25Z) - Evolving Search Space for Neural Architecture Search [70.71153433676024]
最適化された検索空間サブセットを維持することにより,前回の取り組みから得られた結果を増幅するニューラルサーチ空間進化(NSE)方式を提案する。
我々は333万のFLOPでImageNet上で77.3%のトップ1リトレーニング精度を実現し、最先端の性能を得た。
遅延制約が適用された場合、我々の結果は、77.9%のTop-1再トレーニング精度を持つ、以前の最高のパフォーマンスのモバイルモデルよりも優れた性能が得られる。
論文 参考訳（メタデータ） (2020-11-22T01:11:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。