それがどのような競争であり、どのように私たちがそれを勝ち取ることができたのか（そして51カ国から2000以上のソリューションがコンテストに送られた）について読んでください。
私たちのチーム
JBR_HSEチームは、5人のメンバーで構成されていました。KonstantinMakhnev（学士課程「応用数学とコンピューターサイエンス」の4年生で勉強 ）、OlegSvidchenkoとVladimirEgorov（どちらも修士号「プログラミングとデータ分析」で勉強）、博士課程の学生であるDmitryIvanovと 分析センターの責任者 データと機械の学習NRUHSE-サンクトペテルブルクアレクセイシュピルマン。Konstantinを除く全員が、JetBrainsResearchのAgentSystems and Reinforcement Learningラボでも働いています。そのため、チームの名前が付けられました。コンテストに参加している間、Kostyaは同じ研究所で訓練を受けました。
NeurIPS 2020：フラットランド-それは何ですか？
Flatlandは、AIcrowdプラットフォームに基づいて、有名な国際会議NeurIPSによってサポートされ、 7月10日から11月15日に開催されたコンテストです 。競争の目標は、鉄道交通を可能な限りうまく管理できるアルゴリズムを開発することです。重要な制限は、限られた時間（シミュレーターの1ステップあたり5秒）で決定を下す必要があり、最適なアクションを単純に選択することが不可能であったことでした。
NeurIPS 2020：Flatlandには、GeneralとReinforcement Learning（RL）の2つの方向性がありました。最初の領域はあらゆる決定に開かれ、2番目の領域は強化学習を使用する領域にのみ開かれていました。
主催者は参加者にフラットランドシミュレーターを提供しました。これは2次元グリッドであり、各セルには独自のタイプ（道路、曲がり角、分岐点、通行不能な地形）があります。各列車はグリッド上のちょうど1つのセルを占有し、現在移動している方向を持っています。シミュレーションは段階的に実行されます。各列車の各ステップで、実行するアクション（停止、左端のトラックに沿って進む、または右端のトラックに沿って進む）を決定する必要があります。現在の実装では完全な交差点が提供されていないため、右と左を同時に進むことができるということは起こりません。その場合、「進む」というアクションも必要ありません。ターンがない場合、2番目と3番目のアクションは同等です。列車は互いに衝突する可能性があります-それは行き詰まりになります。競争の目標は、すべての列車ができるだけ早く目的地に到着するようにすることです。決定は、列車がゴールに到達するのにかかった時間によって判断されます。列車が到達していない場合、その時間は最大シミュレーション時間に等しくなります。
解決策：エージェントがシミュレーターと対話する方法
強化学習についてはすでにハブレにかなりの数の 投稿がありますので、基本的な概念については詳しく説明しません。Flatlandの場合、鉄道のシミュレーションが環境として機能し、列車がエージェントとして機能するとしましょう。多くの列車がシミュレーションに関与しているため、この環境はマルチエージェントであることに注意することが重要です。
問題を解決する際に、エージェントとシミュレーターの間の相互作用のプロセスを大幅に変更しました。これにより、アルゴリズムの効率を大幅に向上させることができました。一般に、このような変更は結果に大きな影響を与えることがよくありますが、タスク固有の知識が必要です。
最も重要な変更の1つは、エージェントが交差点の近くにいないときに、エージェントに行動の自由を与えないことを決定したことです。したがって、エージェントは、フォークの前またはフォークにいる場合にのみ決定を下すことができ、それ以外の場合は、常に可能な唯一のパスに沿って前進します。これにより、エピソードの期間が大幅に短縮されるため、タスクがはるかに簡単になります。また、エージェントがゴールに到達したとき、またはデッドロックに陥って移動できなくなったときにエピソードを終了することも決定しました（シミュレーターでは、このような場合、エピソードは継続します）。後で、エピソードをすべての人にすぐに開始するべきではないと判断しました。これについては、以下で詳しく説明します。
エージェントの監視は、パスの特定の部分に関連付けられている機能と、パスの特定の部分に関連付けられていない機能の2つの部分で構成されます。ここで、パスの一部とは、2つの分岐点を結ぶ道路のセクションを意味します。
観測の最初の部分はツリーとして表すことができ、その上部にはフォークがあり、エッジはそれらの間の道路です。それがつながる各エッジと頂点に、パスの特定のセクションに対して計算された特徴のベクトルを関連付けます（たとえば、パスの長さ、エッジの端から目的地までの距離など）。ツリーの深さを固定して、観測の最初の部分から取得する特徴ベクトルの数を制限しました。以下は、観測のこの部分がどのように構築されるかの例です。色付きの線は、ツリーの端である道路セクションを表します。
観察の2番目の部分には、目的地までの最小距離、エージェントが交差点にいるのかその前にいるのか、エージェントが行き詰まったなどの兆候が含まれます。エピソードの開始時に各エージェントに識別子（からのランダムな番号0から1）、これはエピソードの残りの間彼と一緒にいて、彼が残りのエージェントとよりよく交渉することを可能にします。観察の両方の部分にエージェント識別子に依存する兆候があります。
エージェントの報酬関数を定義するだけです。いくつかの選択の後、私たちはかなり単純なものに落ち着きました：$ 0.01 \ cdot \ Delta d-5 \ cdot \ text {is \ _deadlocked} + 10 \ cdot \ text {is \ _succeed} $、つまり 報酬は、決定が行われてから目的地までの距離$ d $がどれだけ変化したかを反映し、エピソードが正常に完了した場合は追加の報酬が、デッドロックに達した場合はペナルティがあります。
PPOアルゴリズム
マルチエージェントの問題を解決するために設計された多くの強化学習アルゴリズムがあります。ただし、ベースラインアルゴリズムとしてPPO -Proximal Policy Optimizationアルゴリズムを使用することにしました。これは、 そのコードを再利用してマルチエージェントRLアルゴリズム（COMAなど）を実装できるためです。しかし、後で、PPO（いくつかの変更を加えたもの）自体で問題をうまく解決できることが判明しましたが、マルチエージェント方式の学習ははるかに悪いため、PPOは最終的なソリューションの主要部分であり続けました。
古典的なPPOアルゴリズムは、俳優と批評家の2つの部分で構成されています。批評家は価値関数を概算し、俳優は総報酬の期待値を最大化するランダム化されたポリシー$ \ pi_ \ theta（a | s）$を教えます。
私たちが行った重要な変更の1つは、エージェントが近くのエージェントと通信できるようにするモジュールをアクターアーキテクチャに追加することです。通信プロセスは非常に簡単に構築されます。エージェントは同時にメッセージを生成し、隣接するすべてのトレインに送信します。次に、ネイバーからメッセージを受信した後、加重平均によってそれらを1つのメッセージに結合します。単純な自己注意メカニズムを使用して、メッセージが平均化される重みを決定しました。このようなコミュニケーションプロセスの構築により、学習プロセスを何らかの方法で変更する必要がなくなります。エラーを逆伝播しながら、グラデーションがメッセージを通過できるようにするだけで十分です。
エージェントは自分の隣にあるものだけを観察するため、トレーニング後はより大きな環境でうまく機能すると想定して、小さなマップと少数のエージェントでPPOをトレーニングすることにしました。
どの列車をいつ出発するかをどのように決定しますか？
単純にPPOアルゴリズムを適用しようとしたところ、列車が同時に動き始め、互いに干渉し合うために、ほとんどのデッドロックが発生するという結論にすぐに到達しました。この問題を次の方法で解決しました。同時に少数のエージェントのみを実行し始めました。エージェントの1人がエピソードを終えると、もう1人のエージェントは動き始めることができました。このアプローチでは、列車をどのような順序で発射するかを理解することが重要です。
私たちが試みた最初のアプローチは、目標に最も近いエージェントを立ち上げることでした。小さな環境（短い道路と少数のエージェント）で使用すると、十分に機能しましたが、大規模な環境では、パフォーマンスがはるかに低下しました。したがって、このアプローチはエージェントのトレーニング中にのみ使用することにし、アプリケーション（つまり、テストシステムへの送信）には別のアルゴリズムを使用しました。このアルゴリズムのアイデアは、移動を開始していないエージェントごとに、最後に到達するかどうかを決定する分類子をトレーニングすることです。次に、目的地に正常に到達する確率が十分に大きい場合、エージェントは移動を開始し、そうでない場合は、確率が十分になるまで待機します。
競技結果
その結果、私たちのソリューションはRLトラックで1位、全体で8位になりました。これは、非RLアプローチが現時点ではまだ優れていることを意味しますが、強化学習には可能性があることを示しています。私たちのアプローチにはかなりの数の弱点と未解決の問題（たとえば、大規模な環境へのスケーラビリティに関する深刻な問題）があるため、取り組むべきことがあります。現在、私たちはコンテストの主催者と一緒に、コンテストブックNeurIPS2020に送信するための記事を準備しています。