問題タブ [planning]

これを StackOverflow、cstheory.stackexchange.com、および math.stackexchange.com に投稿しています。どこが最適かよくわからないからです。大丈夫だと思います。

私は2Dグリッドを持っています（サイズはマップごとに異なり、10X10から20X20の範囲で、必然的に正方形です）。各セルには、とりわけ、各ユニット（マップに応じて10から50）がその位置にある確率（0から1）が含まれています位置。

ユニットには主に 2 つのタイプがあります。動作がアルゴリズムによって制御される大きなユニットがあり、あなたが私を助けてくれることを願っています。小さなユニットは、移動するか、(ブール値の) 状態を助けによって変更することしかできません。大きなユニットの。すべてのユニットはチームに属していますが、大きなユニットは小さなユニットを移動できます。試合は、小さなユニットの位置と状態の両方に従って採点されます。各ユニットは独自の座標を知っています。

ポイントは指定された多数のセルのいずれかに小さなユニットを配置することで与えられ、隣接するセルの数に対してボーナスが与えられます - 隣接性は必ずしも隣接するセル座標を意味するわけではなく、マップごとに決定されることに注意してください。

私はすでにパスシステムを持っているので、それは問題ではなく、移動の時間コストを計算することもありませんが、これはパフォーマンス上の理由から最小限に呼び出す必要があります。

私の意図は、計画システムに一連の望ましい状態/アクションを出力させることです。たとえば、43 度の角度で (9,4) にあり、次に 12 度の (12,4) にあり、そこで小さなユニットを有効にします。

時間切れになったときのチームの最終順位を最適化するために、競合する最大 5 つのメイン ユニットのそれぞれに最適な動きを決定しようとしています。ユニットには、確率的な位置を設定するシミュレートされたセンサーがあるため、情報を収集することは有効な動きです。

理想的には、アルゴリズムは数手先を見て、特定の手が次の手を実行するのに適した位置にいるかどうかなどを考慮します。この位置の「良さ」は、パス コストの逆数になります。

ここではパフォーマンスが非常に重要であり、大幅なパフォーマンスの向上と引き換えにソリューションの品質を犠牲にすることを厭わないかもしれません。

これまでの私の考えは次のとおりです。

• 最も完全な解決策は徹底的な検索ですが、パフォーマンスがこれを除外します。

• どの情報が重要かを判断できるように、合理的に考えられる現在の状態のそれぞれの重要性を計算する必要があります。

• 平均的な最新の PC でのユニットあたりの実行時間は、可能であれば <= 25 ミリ秒にする必要があります。これは C++ であるため、かなり高速です。

• チェスのアルゴリズムを適応させることは、良いアプローチかもしれません。

• 苦手なので、ネットで聞いてください。

• 最良のアプローチは、ほぼ間違いなく見積もりです。

• 1 つの手が他の手より 20 倍のポイントを獲得する可能性が 10% ある場合、リスクを冒す価値があります - 他の手が良い最終順位をほぼ保証し、時間切れが近づいている場合を除きます。

• 私の質問はやや冗長です。

• 今までもっと考えていたに違いない気がしますが、それが何であるかを一生考えることができません。

• その最後の点は韻を踏んだ。

• あなたがまだこれを読んでいるなら、私はあなたと結婚したいと思うかもしれません。

誰かがこれに対する完全な解決策を提供してくれたら素晴らしいことですが、私が得ることができるあらゆる助け/ヒントを受け入れることを絶対に喜んでおり、それが遠いかどうかに関係なく、私を最も遠ざける答えを受け入れます. 私が興味を持っているのは、コードよりもアルゴリズムです。私は今では大柄な女の子なので、自分で処理できます。

私はフォワード プランニング ヒューリスティック hmax、hadd、および hff を研究しており、オンラインでいくつかのリソースを見つけましたが、それらが実際にどのように機能するかを本当に理解できません。

これまでに見つけたリソースは次のとおりです。

http://icaps09.uom.gr/tutorials/tut1.pdf
(hmax、hadd、hff、およびh+.)

http://gki.informatik.uni-freiburg.de/papers/betz-helmert-icaps2009ws.pdf
(Betz と Helmert による科学論文で、AI 2009 に関するドイツ会議で「Planning with h+ in Theory and練習」は、他の3つと密接に関連しています。)

https://cw.felk.cvut.cz/wiki/_media/courses/a4m36pah/07_relaxation.pdf
(ヒューリスティック hmax、hadd、hff に関する別のチュートリアル (ソース不明))

それらがどのように機能するかを簡単に説明できますか? ありがとうございました

ループに入ったりアクションを繰り返したりしないように STRIPS を変更するにはどうすればよいですか? A - B - C - D - E の領域 (トラバース問題) があるとしましょう。それらはすべて双方向です。初期状態は At(A) であり、目標は At(E) になる必要があることです。結果は

Travel(C, B) - Travel(B, C) - Travel(C, D) - Travel(D, E).

要するに、A - B - C - D - C - B - C - D - E と進みました。これを解決する方法と、より良い疑似コードを提供できるかどうかについてのアイデアが必要です。ありがとう！

このトピックは初めてです。現在、計画、制約解決、推論の違いについて少し混乱しています。

私が理解している限り、計画とは、行うべき正しい「こと」を特定することです。

これは、いくつかの共制約に従うことで実行できます。では、各計画の問題が最終的に csp であるというのは正しいのでしょうか?

では、計画は csp 問題のサブセットですか?

推論は、「ウサギが生命体である」場合のような大規模なオントロジーに対するクエリにすぎません。

アクションとモーションプランニングの違いを理解するのに苦労しています。モーション プランニングには、モバイル エージェントの軌跡を見つけることだけが含まれますか?

私は、STRIPS 形式で与えられた AI 計画の表現に関するいくつかの資料を検討しており、さまざまな人が同じ問題をさまざまな方法で定式化しているように見えることがわかりました。

たとえば、ウィキペディアには、実験室でのサルの問題に関する例があります。問題は次のように述べています。

サルが天井からぶら下がっているバナナに登ると、サルがバナナに到達できるようにするボックスが用意されています。最初は、サルはA、バナナはB、ボックスはCです。サルとボックスの高さは低ですが、サルがボックスに登ると、バナナと同じ高さになります。サルが利用できるアクションには、ある場所から別の場所への移動、ある場所から別の場所へのオブジェクトのプッシュ、オブジェクトへの ClimbUp または ClimbDown、およびオブジェクトの Grasp または UnGrasp が含まれます。サルと物体が同じ高さの同じ場所にある場合、物体をつかむことは物体を保持することになります。

これがウィキペディアの計画です (この問題の説明と正確には一致していませんが、同じ問題であることに注意してください。Ungrasp を実装していないようです。これはこの議論では重要ではありません)。

この計画のどこにもバナナがレベル (高) にあることがわかりません。したがって、これを実際に計画から明らかにする唯一の方法は、アクションのセット全体を読み、そこからモンキーがバナナと対話するには Level(high) にあるため、バナナは Level(high) にある必要があります。

この情報を初期状態に置き、次のようにすることをお勧めします。

サル(m) & バナナ(ba) & ボックス(bx) & レベル(低) & レベル(高) & 位置(A) & 位置(B) & 位置(C) & At(m, A, low) & At (ba, B, 高) & At(bx, C, 低)

このように非常に冗長に見えますが、同時に、読者は初期状態を読むだけでシナリオを理解できます。また、STRIPS のどこにも定数を使用すべきではないと言われたので、A、B、および C を位置として宣言するのは良い考えだと思いました。

一部の人々が別の方法でそれを行うのでしょうか (標準化された言語で物事を表現するという考えが台無しになると思います)、それとも私が提示した方法の 1 つが正しい形式ではないのでしょうか? 私は STRIPS を初めて使用するので、いくつかの重要なポイントが欠けている可能性が十分にあります (そしてその可能性が高いです)。

4、5 行目 (および E は何に使用されますか?)、9 行目 (どのように選択されますか?)、および 10 行目を理解するのに苦労しています。

ご協力いただきありがとうございます。

象徴的な計画の問題を解決するために、私たちは行動理論を書きます。行動理論を書くための一般的な言語は、STRIPS と ADL です。

アクションを説明するために、以下を提供する必要があります。

• 前提条件
• 効果

たとえば、ロボット ドメインには、RobotandObjectクラスとcloseToandholdingプロパティがあります。

ホールドすればアクションpickUp(?robot, ?object)が可能closeTo(?robot, ?object)で、さらにforall ?o in Object . not holding(?robot, ?o).

OWLおよび/またはSWRLで前提条件をどのように表現しますか?

アクションエフェクトはどうですか？

生産システムのスループットを改善しようとしています。システムの正確なタイプは関係ありません (私は思います)。

説明

1. このシステムは、ステーションのLINE (番号 1、2、3...) とARMで構成されています。
2. システムは、ランダムな時間にITEMを受け取ります。
3. 各ITEMには、それに関連付けられたPLANがあります (たとえば、ITEM1には、ステーション 3、次に 1、次に 5 を通過する必要があるというPLANがある場合があります)。PLANには、 ITEMが各ステーションに留まる時間に関するタイミング情報(ハード最大/最小値の範囲) が含まれています。
4. 各STATIONは、一度に 1 つのITEMを保持できます。
5. ARMは、各ITEMを 1 つのSTATIONから次の STATION に移動するために使用されます。各PLANには、固定値であるARMのタイミング情報も含まれています。

現在の習慣

2 つの現在の (作業中の) 計画ソリューションがあります。

1 つ目は、各STATIONの使用状況のマスター リストを維持します。これを「予約」アプローチと考えてください。新しいITEM-Nが入力されるたびに、システムはPLAN-Nが適合する最も早いスロットを見つけるために前方を検索します 。したがって、たとえば、t = 0 で適合させようとし、適合が見つかるまで遅延を徐々に増やしていきます (実際には、処理時間を短縮するためのヒューリスティックがいくつかありますが、アプローチは有効です)。

2 つ目は、いつ開始するかを指定する各ITEMのリストを維持します。新しいITEM-Nが入ると、システムはそのPLAN-Nを既存のすべてのリスト と比較して、開始するのに適した時期を見つけます。繰り返しますが、t=0 で開始し、徐々に遅延を増やしていきます。

2 つのソリューションのどちらも、ITEMが各ステーションで許可される時間の範囲を利用していません。一定の時間が想定されます (中間点または最小値)。

理想的なソリューション

現在のITEMの一部が特定のSTATIONで費やす期間を変更した場合、その期間を短縮するかどうかに関係なく (新しいITEMが入ることができるように代わりにステーション）またはその期間を長くする（したがって、ARMはITEMを移動する時間があり ます）。

問題に遺伝的アルゴリズムのソリューションを実装しようとしています。現在の遺伝子には N 個の数字 (0 から 1 の間) が含まれています。ここで、N は現在システム内にあるすべてのアイテムと追加される新しいアイテムの合計ステーション数です。この遺伝子を実際の期間に変換するのは簡単です。 (0 は最小持続時間、1 は最大持続時間、その間を直線的にスケーリングします)。

ただし、この遺伝子表現は、互いに重複する使用できない計画を一貫して生成します。この理由は、複数の項目がすでに理想的に配置されている場合 (時間的に連続し、計画的に)、期間の変更は不可能だからです。アイテムがすでに処理されていると、遅延または前倒しできないため、これは避けられません。

上記の状況の例として、ITEMAがt1 から t2 および t3 から t4 の間STATION3にあるとします。その後、ITEMBが出現し、t2 から t3 の間、STATION3 を占有します (したがって、STATION3は t1 と t4 の間で完全に使用されます)。私の現在の遺伝子表現では、重複を生成しないように、遺伝子の特定の要素が正確に正しい値を持つ必要があるため、有効な解決策を見つけることは事実上保証されていません。

質問

1. 上記よりも優れた遺伝子表現はありますか?
2. 変更可能なタイミングを見つけるために、簡単な山登りをした方がよいでしょうか? それとも、GAは実際にこの問題に適していますか?

私はpddlが初めてです。ロボットがさまざまなオブジェクトをさまざまな宛先セルに配置できるソリューションを見つける必要があります。http://www.fast-downward.org/のソフトウェアを使用しています。ただし、問題は、私の行動が必要な解決策を見つけられないことです。制限は、ロボットが物体を運んでいても、2 つの物体を同じ部屋に置くことはできないということです。添付: ドメイン ファイル:

および問題のファイル: