論文の概要: Unlucky Explorer: A Complete non-Overlapping Map Exploration
- arxiv url: http://arxiv.org/abs/2005.14156v1
- Date: Thu, 28 May 2020 17:19:24 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-27 05:37:14.361006
- Title: Unlucky Explorer: A Complete non-Overlapping Map Exploration
- Title（参考訳）: Unlucky Explorer: 完全な非オーバーラップマップ探索
- Authors: Mohammad Sina Kiarostami and Saleh Khalaj Monfared and Mohammadreza
Daneshvaramoli and Ali Oliayi and Negar Yousefian and Dara Rahmati and Saeid
Gorgin
- Abstract要約: エージェントがすべてのセルを訪問するハミルトニアンパスを見つけなければならない探索問題として,Maze Dashパズルを紹介した。
提案したモンテカルロ木探索(MCTS)アルゴリズムに最適化を適用し,有望な結果を得た。
比較の結果,MCTSをベースとしたアプローチは,テストケースの小型化と中型化を両立させる手法であることがわかった。
- 参考スコア（独自算出の注目度）: 0.949996206597248
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Nowadays, the field of Artificial Intelligence in Computer Games (AI in
Games) is going to be more alluring since computer games challenge many aspects
of AI with a wide range of problems, particularly general problems. One of
these kinds of problems is Exploration, which states that an unknown
environment must be explored by one or several agents. In this work, we have
first introduced the Maze Dash puzzle as an exploration problem where the agent
must find a Hamiltonian Path visiting all the cells. Then, we have investigated
to find suitable methods by a focus on Monte-Carlo Tree Search (MCTS) and SAT
to solve this puzzle quickly and accurately. An optimization has been applied
to the proposed MCTS algorithm to obtain a promising result. Also, since the
prefabricated test cases of this puzzle are not large enough to assay the
proposed method, we have proposed and employed a technique to generate solvable
test cases to evaluate the approaches. Eventually, the MCTS-based method has
been assessed by the auto-generated test cases and compared with our
implemented SAT approach that is considered a good rival. Our comparison
indicates that the MCTS-based approach is an up-and-coming method that could
cope with the test cases with small and medium sizes with faster run-time
compared to SAT. However, for certain discussed reasons, including the features
of the problem, tree search organization, and also the approach of MCTS in the
Simulation step, MCTS takes more time to execute in Large size scenarios.
Consequently, we have found the bottleneck for the MCTS-based method in
significant test cases that could be improved in two real-world problems.
- Abstract（参考訳）: 現在、コンピュータゲームにおける人工知能(AI in Computer Games)の分野は、コンピュータゲームが幅広い問題、特に一般的な問題でAIの多くの側面に挑戦するため、より順調に進んでいる。
このような問題の1つは探索であり、未知の環境を1つまたは複数のエージェントによって探索する必要がある。
本研究では, エージェントがすべてのセルを訪問するハミルトニアンパスを見つけなければならない探索問題として, Maze Dashパズルを導入した。
そこで我々は,モンテカルロ木探索(MCTS)とSATに着目し,この問題を迅速かつ正確に解くための適切な手法を探索した。
提案したMCTSアルゴリズムに最適化を適用し,有望な結果を得た。
また,本パズルの事前作成されたテストケースは,提案手法を検証できるほど大きくないので,そのアプローチを評価するために,解決可能なテストケースを生成する手法を提案し,活用した。
最終的に、MCTSベースの手法は自動生成テストケースによって評価され、実装されたSATアプローチと比較された。
比較の結果,MCTS ベースのアプローチは,SAT と比較して高速な実行時間で,中小のテストケースに対処できる,先進的な手法であることが示唆された。
しかし,問題の特徴,木探索機構,シミュレーションステップにおけるMCTSのアプローチなど,特定の理由から,MCTSは大規模シナリオの実行により多くの時間を要する。
その結果、2つの実世界の問題で改善できる重要なテストケースにおいて,mctsに基づく方法のボトルネックが見つかった。
関連論文リスト
- POGEMA: A Benchmark Platform for Cooperative Multi-Agent Navigation [76.67608003501479]
主評価指標の基礎に基づいて計算された領域関連メトリクスの範囲を定義する評価プロトコルを導入・指定する。
このような比較の結果は、様々な最先端のMARL、検索ベース、ハイブリッド手法を含むものである。
論文 参考訳（メタデータ） (2024-07-20T16:37:21Z) - Robustness Assessment of Mathematical Reasoning in the Presence of Missing and Contradictory Conditions [48.251724997889184]
我々は、ミス・コントラクタリー条件(PMC)に関する問題というベンチマークを開発する。
本稿では,これらのシナリオにおける数ショットプロンプト手法の性能を評価するための2つの新しい指標を提案する。
SMT-LIB Prompting (SLP) と呼ばれる,SMT-LIB言語を用いて直接解決する代わりに,この問題をモデル化する手法を提案する。
論文 参考訳（メタデータ） (2024-06-07T16:24:12Z) - Amplifying Exploration in Monte-Carlo Tree Search by Focusing on the
Unknown [19.664506834858244]
モンテカルロ木探索(MCTS)は、探索木の有望なセグメントに焦点を合わせるために、戦略的に計算資源を割り当てる。
提案手法はAmEx-MCTSと呼ばれ,新しいMCTSの定式化を導入することでこの問題を解決する。
実験による評価は,AMEx-MCTSの優れた性能を示し,従来のMCTSと関連するアプローチを実質的なマージンで上回っている。
論文 参考訳（メタデータ） (2024-02-13T15:05:54Z) - Robust Analysis of Multi-Task Learning Efficiency: New Benchmarks on Light-Weighed Backbones and Effective Measurement of Multi-Task Learning Challenges by Feature Disentanglement [69.51496713076253]
本稿では,既存のMTL手法の効率性に焦点をあてる。
バックボーンを小さくしたメソッドの大規模な実験と,MetaGraspNetデータセットを新しいテストグラウンドとして実施する。
また,MTLにおける課題の新規かつ効率的な識別子として,特徴分散尺度を提案する。
論文 参考訳（メタデータ） (2024-02-05T22:15:55Z) - LightZero: A Unified Benchmark for Monte Carlo Tree Search in General
Sequential Decision Scenarios [32.83545787965431]
学習モデルを用いた木探索計画能力に基づくエージェントの構築は、GoやAtariといった古典的な意思決定問題において大きな成功を収めている。
モンテカルロ木探索(MCTS)ベースのアルゴリズムを様々な現実世界のアプリケーションに拡張することは困難または不可能であるとみなされている。
本稿では,MCTS/MuZeroを一般的な逐次決定シナリオに展開するための最初の統一ベンチマークであるLightZeroを紹介する。
論文 参考訳（メタデータ） (2023-10-12T14:18:09Z) - Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
マルチエージェントパスフィンディングに適したモンテカルロ木探索(MCTS)のオリジナル版を紹介する。
具体的には,エージェントの目標達成行動を支援するために,個別の経路を用いる。
また,木探索手順の分岐係数を低減するために,専用の分解手法を用いる。
論文 参考訳（メタデータ） (2023-07-25T12:33:53Z) - Spending Thinking Time Wisely: Accelerating MCTS with Virtual Expansions [89.89612827542972]
本稿では,モンテカルロ木探索 (MCTS) の変種を提案する。
9倍のGoボードゲームとAtariゲームの性能と計算結果を評価した。
実験の結果,提案手法は,平均検索時間50%以下で,元の検索アルゴリズムに匹敵する性能が得られることがわかった。
論文 参考訳（メタデータ） (2022-10-23T06:39:20Z) - Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。
SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。
本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。
ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
論文 参考訳（メタデータ） (2021-09-13T18:10:52Z) - Monte Carlo Tree Search: A Review of Recent Modifications and
Applications [0.17205106391379024]
モンテカルロツリー検索(MCTS)は、ゲームプレイボットを設計したり、連続的な決定問題を解決するための強力なアプローチです。
この方法は、探索と搾取のバランスをとるインテリジェントな木探索に依存している。
しかし、この方法はより複雑なゲームでは最先端の技術となっている。
論文 参考訳（メタデータ） (2021-03-08T17:44:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。