問題タブ [planning]

私は、地元の学校の簡単な計画ツールとして機能する必要がある小さなソフトウェア アプリケーションを作成しています。解決する必要がある「問題」はかなり基本的なものです。つまり、教師はすべての子供の親と話をする必要があります。ただし、もちろん、兄弟姉妹が別のグループにいる子供もいます。そのため、両親が午後 6 時に話し、午後 10 時に別の話しをするという状況を避けるために、これらの話し合いを隣り合わせにスケジュールする必要があります。つまり、 1 人以上の兄弟または姉妹がいるn人の子供のコレクションが与えられた場合、これらの子供のすべての話が隣り合って計画されるスケジュールを生成します。

さて、問題は非常に簡単に解決できるかもしれませんが、一方で、これはかなり複雑な問題になる可能性があり、何らかのアルゴリズムが必要であり、解決できると感じています。エレガントに。しかし、私は正しいですか？ある？ハンガリーのアルゴリズムを見てきましたが、この特定の問題にはまったく当てはまりません。

編集: 言い忘れていましたが、すべてのトークには同じ時間がかかります。

ありがとう！

PythonまたはJavaで実装された階層型タスクネットワークプランナーを知っている人はいますか？私はいくつかのオープンソースシステムを見つけましたが、それらはすべて一見死んだプロジェクトであり、何年も維持されていません。

単純なSTRIPSベースのプランナーを作成しようとしています。目標に到達する個別の確率的計画を計算するための基本機能を完了しましたが、現在、最初のアクションに基づいてこれらの計画を集約する方法を決定し、時間t0での「全体的な」最良のアクションを決定しようとしています。 。

次の例を考えてみましょう。ユーティリティは、0から1の範囲で、計画が目標をどの程度達成しているかを表します。CFも0と1の間にあり、確実性係数、つまり計画を実行すると特定の効用が得られる確率を表します。

相互に排他的な3つのプランすべてが、アクションA1で始まる場合、アクションA1を使用するための全体的な「適合性」を判断するために、それらをどのように集約する必要がありますか？私の最初の考えは、確実性の要因を合計し、それをユーティリティの平均で乗算することです。それは正しいと思いますか？

したがって、現在の結果は次のようになります。

または、個々の可能性のあるユーティリティを計算し、それらを平均する必要がありますか？

より理論的に健全な方法はありますか？

グリッド内の 2 つのノード間のすべてのパスを見つけようとしていますが、パスは最初から最後まですべてのノードを通過する必要があります。例 (開始 = S、終了 = E)

0 0 0
0 S 0
0 0 エ

上記の答えは 2 つのパスです: (「.」は無視してください)

0-0-0
|.......|
0 S-0
|
0-0-E

0-0-0
|……|
0 S 0
|...|...|
0-0 日

再帰を使用することを考えましたが、各呼び出しのオーバーヘッドが高いためにそれをあきらめました...そして、スタックを使用した反復アプローチを採用することにしました。（再帰のようなものですが、そうではありません...固定メモリオーバーヘッド）。このソリューションは、サイズ (4x7) のグリッドでうまく機能しますが、8x8 グリッドで試してみました...そして 4 時間で終了しませんでした...可能性の合計数が約 3 ** であるため、これは理にかなっていますエッジ上にない各ノードには 3 つのトラバーサル方法があるため、そのソリューションは失敗します。

縦と横の分割を使用して 8x8 グリッドを 2 つに分割することを考えましたが、これは理想的とは言えないパスを見つけることにつながります。

私が見逃しているものはありますか???? それを速くするために何かできることはありますか？明日の解決策を投稿します（Cで行います）。

現代のOWL/RDF推論システムと、古いSTRIPSスタイルの自動プランナーおよびスケジューラーとの間の交差点として機能するソフトウェアはありますか？どちらのシステムもRETEベースのパターンマッチングを利用していますが、「アクション」の概念を形式化するのは自動化されたプランナーだけのようです。残念ながら、GraphplanやSOARなど、自動計画を実装していることがわかったすべてのプロジェクト、死んでいるか死にかけているようであり、そもそもうまくスケーリングするようには見えませんでした。現在のデータストアはRDMSに実装されており、数百万を超えるトリプルに拡張して推論することができますが、アクションを具体的に試みて推論するものは見つかりませんでした。アクションの概念が従来のRDFでどのように表現されるかを想像することはできますが、公式のサポートがなければ、それでも非常に複雑でハックになると確信しています。残念ながら、私は多くの先行技術を見つけることができません。これは以前に行われたことがありますか？

すべての強化学習私が読んだアルゴリズムは通常、一定数のアクションを持つ単一のエージェントに適用されます。可変数のアクションを考慮しながら決定を下すための強化学習アルゴリズムはありますか? たとえば、プレーヤーが N 人の兵士を操作し、各兵士がその状態に基づいてランダムな数のアクションを行うコンピューター ゲームに RL アルゴリズムをどのように適用しますか? グローバルな意思決定者 (つまり、「将軍」) に対して固定数のアクションを定式化することはできません。これは、兵士が作成されたり殺されたりするにつれて、使用可能なアクションが絶えず変化するためです。また、兵士の行動は周囲の環境に基づいて条件付けられるため、兵士レベルで一定数の行動を定式化することはできません。兵士が敵を見ていない場合、歩くことしかできないかもしれませんが、

複数のレストラン（たとえば20）へのフードデリバリーを想定しましょう。利用可能な（たとえば10個の）ドライバーがあります。さらに、これらのレストランから家庭に食べ物を配達するために、4時間で100件の注文があったとします。

そのため、ドライバーは、ある場所で食べ物を受け取り、自宅の顧客に配達するように調整する必要があります。

主な目標は、配達までの時間、つまり注文から自宅に到着するまでの時間を最小限に抑えることです。2番目の目標は、ドライバーの容量を最大化することです（つまり、すべての注文を配信するための最小時間）。

注文は4時間以上かかるので、均等に、つまり3分ごとに注文することに注意してください。また、注文がランダムに20軒のレストランに向けられていると仮定します。

任意の場所から目的地、そして秒までの移動時間を計算できると仮定します。

私はすべてのドライバーの位置をリアルタイムで知っています。私は彼らのステータスも知っています。つまり、彼らは現在注文を受け取る途中（既知の目的地に行くため）であり、すでに注文を受け取り、既知の目的地に向かう途中ですか。

制約は次のとおりです。1）指定された時間の後に注文を受け取る必要があります（つまり、レストランの食事の準備時間）2）45分以内に注文を配信する必要があります（それ以外の場合はアラートがスローされます）3）時間に対応するために「x」分で時間を埋める必要があります注文を受け取るために店まで歩いて過ごしたなど。4）顧客への注文の配送と支払いの回収に費やした時間に対応するために、時間を「y」分で埋める必要があります。5）ドライバーは、特定の支払い方法のセット（Cash、Visa、Amex、MasterCardなど）しか持っていません。顧客の要求（現金、ビザなど）とドライバーの能力（現金、ビザ、アメックスなど）を一致させる必要があります。

したがって、たとえば、目的地の近くと集荷場所の近くで2つの注文を受け取った場合、別の「無料」ドライバー（何もしていない）があったとしても、同じドライバーを使用して両方の注文を集荷して配達する方が効率的です。両方の注文。

各レストランに配達ゾーンが適用されると想定できます。つまり、レストランから注文するほとんどの人は、レストランの近くにいる可能性があります。したがって、このアルゴリズムは、ドライバーを自動的に都市ゾーンにセグメント化し、ゾーン内のドライバーをすでに優先するように管理する必要があります。

私は C でいくつかの AI 計画アルゴリズムを実装しようとしていますが、基本的な概念に行き詰まりました :)
主な問題にジャンプする前に、命題論理をサポートするいくつかの小さなフレームワークを実装してみました:

さて、問題は、式を定義する瞬間に 'a + 3 > 0' のような式を評価するのではなく、後の段階で評価したいということです:

この場合、クロージャーが便利だったと思いますが、残念ながら私は C99 に固執したいと思っています。

何か案が ？
これを述語ロジックに拡張するのはどうですか？

最終的な目標 (理想的には) は、アプリケーションに直接プラグインできる AI プランニング ライブラリを構築し、問題を STRIPS プログラム文字列として受信しないようにすることです。

ありがとう

道路の相互接続と推定運転時間を表すグラフを取得し、Python を使用して解析するにはどうすればよいでしょうか?

演習として、基本的な A* プランナーを実装して、地図上の 2 点 (つまり、TomTom、Garmin、Google Nav など) の間を移動するためのルートをプロットしようとしています。モックアップすることもできますが、できれば本物の地図データを使いたいです。

私はOpen Street Mapを知っており、地図の小さなスライスを OSM XML データにエクスポートすることはできますが、これを使用できる形式で簡単に解析するツールを見つけるのに苦労しています。私はimposmを見つけましたが、他にはあまりありません。他のツールを推奨できる人はいますか?

タスクの最適なスケジュールを作成するためのツールを知っている人はいますか? 複数のデータベースを実行している多数のサーバーがあり、各データベースとの間でデータをインポートおよび変換するさまざまなスクリプトがあります。

私は現在、さまざまな cron ジョブを手動でスケジュールしていますが、これはエラーが発生しやすく、データ負荷が異常に大きいためにジョブの実行に異常に時間がかかるなどの例外を考慮するのが困難です。各タスク間のリソースと依存関係をエンコードし、最適なタスク実行シーケンスを検索するプランナーを作成して、各タスクが他のタスクに干渉する可能性が最も低い時間に実行されるようにすることを検討しています。

Drools Plannerを見たことがありますが、非常に複雑でオーバーヘッドが大きいため、適切ではありません。