JP7776007B2 - 経路探索装置、制御方法及びプログラム - Google Patents

Description

本発明の開示は、概してマルチエージェント経路探索問題に関する。

マルチエージェント経路探索（MAPF: multi-agent path finding）問題は、総移動距離など、単一の目的を最適化しながら、複数の車両が経路に沿って移動する場合に、車両が互いに又はいかなる静的障害物とも衝突しないように、複数の車両の各々について経路を探索する問題である。非特許文献１には、MAPF 問題を解決するためのコンフリクトベース探索（CBS: Conflict Based Search）アルゴリズムと呼ばれるアルゴリズムが開示されている。CBS は、高レベル探索と低レベル探索とに分けられる２レベルの探索アルゴリズムである。高レベル探索では、CBS は、二進木と呼ばれる制約木（CT: constraint tree）を使用して、車両間の衝突を回避するための車両の時間と位置に関する適切な制約を求める。低レベル探索では、CBS は、高レベル探索で求められた制約の下で各車両の経路を探索する。

非特許文献１により開示されている CBS アルゴリズムは、単一の目的、すなわち経路長に基づいて経路を評価するため、複数の目的を扱うことができない。非特許文献２は、複数の目的を処理するように CBS を拡張した多目的コンフリクトベース探索（MO-CBS: multi-objective conflict-based search）と呼ばれるアルゴリズムを開示している。複数の目的を処理する MAPF 問題の一般化は、「多目的 MAPF （MOMAPF: multiple-objective MAPF）」と呼ばれることに留意されたい。MO-CBS は、その各々が初期パレート最適解を含むルートノードを有する複数の CT を生成する。ルートノードでは、車両間の衝突は考慮されない。その後、検出された衝突を解決するために子ノードを生成する。また、この手法では、所定のコストを有するグラフを考慮する。

Guni Sharon、Roni Stern, Ariel Felner、及び Nathan R. Sturtevant、「最適なマルチエージェント経路探索用のコンフリクトベース探索」、Elsevier、Artificial Intelligence、Volume 219、40-66 ページ、２０１５年２月 Zhongqiang Ren、Sivakumar Rathinam、及び Howie Choset、「マルチエージェント経路探索用の多目的コンフリクトベース探索」、［online］、２０２１年１月１１日、［２０２１年１２月７日検索］、＜arXiv, https://arxiv.org/pdf/2101.03805v2.pdf＞から取得 Wei Chu 及び Zoubin Ghahramani、「ガウス過程による優先度学習」、ACM、the 22nd International Conference on Machine Learning、２００５年８月７日 Eric Brochu、Vlad M.Cora、及び Nando de Freitas、「アクティブユーザモデリング及び階層強化学習への応用を伴う高価コスト関数のベイズ最適化に関するチュートリアル」、［online］、２０１０年１２月１２日、［２０２１年１０月６日検索］、<arXiv, https://arxiv.org/pdf/1012.2599.pdf>から取得

MO-CBS は、複数のパレート最適解を計算しなければならないため、計算コストが高い。本発明の開示の目的は、複数の目的を考慮に入れながら、複数車両向けの経路の集合を提供するための計算コストがより小さい方法を提供することである。

本開示の経路探索装置は、少なくとも１つのプロセッサと、命令を記憶するメモリと、を備える。前記少なくとも１つのプロセッサは、前記命令を実行して、車両情報及び地図情報を取得し、前記車両情報は複数の車両の各々について開始位置と目標位置の組を示し、前記地図情報は前記車両が移動する空間の地図を示し、前記車両情報と前記地図情報とを使用して、前記車両の各々について経路を含む経路集合を決定し、前記経路集合の前記経路は互いに競合しないように構成され、前記経路集合の前記決定は、経路計画アルゴリズムを実行して前記車両の各々について前記経路を生成することを含み、前記経路計画アルゴリズムは、複数の目的が前記経路によって最適化される度合いを表すスカラー値である前記経路の効用スコアに基づいて、前記経路を評価する。

本開示の制御方法は、コンピュータによって実行される。当該制御方法は、車両情報と地図情報を取得することを含み、前記車両情報は複数の車両の各々について開始位置と目標位置の組を示し、前記地図情報は前記車両が移動する空間の地図を示し、前記車両情報と前記地図情報を使用する前記車両の各々についての経路を含む経路集合を決定することを含み、前記経路集合の前記経路は互いに競合せず、前記経路集合の前記決定は、経路計画アルゴリズムを実行して、前記車両の各々について前記経路を生成することを含み、前記経路計画アルゴリズムは複数の目的が前記経路によって最適化される度合いを表すスカラー値である前記経路の効用スコアに基づいて、前記経路を評価する。

本開示の非一時的なコンピュータ可読記憶媒体は、前述した本開示の制御方法をコンピュータに実行させるプログラムを格納する。

本発明の開示によれば、複数の目的を考慮に入れながら、複数車両向けの経路の集合を提供するための計算コストがより小さい方法が提供される。

実施形態１の経路探索装置の概要を示す図である。 経路探索装置の機能構成の一例を示すブロック図である。 経路探索装置を実現するコンピュータのハードウェア構成の一例を示すブロック図である。 実施形態１の経路探索装置が実行する処理の一例を示すフローチャートである。 車両情報の構造の一例をテーブル形式で示す図である。 CBS の全体のフローを示すフローチャートである。 MAPF 求解部が実行する GA 経路プランナのフローの一例を示すフローチャートである。 交差ステップの一例を示す図である。 変異に対する候補経路からウェイポイントの削除を示す図である。 変異に対する候補経路への１つ以上のウェイポイントの追加を示す図である。 変異に対する候補経路への１つ以上のウェイポイントの追加を示す図である。 実施形態２の経路探索装置の概要を示す図である。 実施形態２の経路探索装置の機能構成の一例を示すブロック図である。 実施形態２の経路探索装置が実行する処理の一例を示すフローチャートである。 経路集合の複数候補を視覚的に提示する図である。

以下、本発明開示の例示的な実施の形態について、図面を参照しながら説明する。各図面において同一の要素には同一の符号を付し、必要に応じて重複する説明を省略する。さらに、記憶部は、１つ以上の記憶装置で形成される。

実施形態１
＜概要＞
図１は、実施形態１の経路探索装置２０００の概要を示す図である。なお、図１に示す概要は、経路探索装置２０００を分かりやすくするために経路探索装置２０００の動作の一例を示したものであり、経路探索装置２０００が取り得る動作の範囲を限定したり狭めたりするものではない。

経路探索装置２０００は、車両集合１０についての経路集合４０を生成するように動作する。経路集合４０は、経路５０の集合であり、車両集合１０に含まれる複数の車両２０の各々に対する経路５０を含む。各車両２０は、その対応する経路５０に沿ってその開始位置からその目標位置まで移動するように構成される。

車両集合１０は、Ｎ台の車両｛ｖ１，．．．，ｖＮ｝を含むものとする。経路探索装置２０００は、車両集合１０に対する経路集合｛ｐ１，．．．，ｐＮ｝を生成する必要があり、経路ｐｉは、１からＮまでの各ｉの車両ｖｉに対応する。

車両集合１０は、車両２０の集合であり、エンティティ３０に関連付けることができる。エンティティ３０は、車両集合１０の責任を負う任意のエンティティであってよい。例えば、エンティティ３０は、車両集合１０内の車両２０のオペレータ又は車両集合１０を所有する若しくは管理する会社であってもよい。

車両２０は、その対応する経路５０に沿って移動するのに制御可能な任意の移動物体であってよい。いくつかの実装形態では、車両２０は、無人搬送車（AGV: automatic guided vehicle）、ドローンなど、任意の種類の自律車両であってよい。他の実装形態では、車両２０は、手動で操作する任意の種類の移動物体であってもよい。

開始位置及び目標位置は、各車両２０に対して予め定義する。車両２０の開始位置及び目標位置を知るために、経路探索装置２０００は、車両集合１０内の各車両２０の開始位置及び目標位置を示す車両情報６０を取得することができる。

経路集合４０の生成に関して少なくとも２つの要件がある。まず、経路集合４０は競合がないこと、すなわち、各経路５０は、経路集合４０内の他の経路のいずれとも競合しないことが要求される。第二に、経路集合４０を、複数の予め定義された目的が実質的に最適化されるように生成する必要がある。考えられ得る様々な目的がある。目的に関するいくつかの例には、経路集合４０内の経路５０の効率性、安全性、及び平滑性がある。これらの目的については、後で詳細に説明する。

上述した少なくとも２つの要件を満たす経路集合４０を見つけるために、経路探索装置２０００は、多目的マルチエージェント経路探索（MOMAPF: multi-objective multi-agent path finding）問題を解くことによって経路集合４０を生成する。以下、経路探索装置２０００が MOMAPF 問題を解くために実行するアルゴリズムを、「MOMAPF ソルバ」と呼ぶ。MOMAPF ソルバは、上記の２つの要件、すなわち競合がないこと、及び複数の目的を実質的に最適化することを満たす経路集合４０を見出すまで、経路集合４０を繰り返し生成する。

解決すべき MOMAPF 問題を定義するために、（１）車両２０が移動することができる空間の地図、及び（２）各車両２０の開始位置及び目標位置が、少なくとも必要である。（１）に関して、経路探索装置２０００は、車両２０が移動することができる空間の地図を示す地図情報７０を取得する。（２）については、前述したように、車両情報６０には、各車両２０の開始位置及び目標位置が示されている。

第２の要件を満たすために、経路探索装置２０００は、各経路５０の効用を考慮する。経路５０の効用は、複数の目的の観点から、経路５０が良好であるほど高くなるように定義される。経路探索装置２０００は、経路５０によって複数の目的が最適化される度合いを表す経路５０の効用スコアを計算するように定義された効用関数を使用して、経路５０の効用を測定する。後に詳述するように、効用関数は、その対応する目的を最適化する度合いを各々が表す複数の目的項についての重み付きの和として、定義してもよい。

MOMAPF ソルバが各経路５０の効用を評価できるようにするために、MOMAPF ソルバは、メタヒューリスティックアルゴリズム（例えば、進化的アルゴリズム（EA: evolutionary algorithm））、ヒューリスティック探索アルゴリズム、しらみつぶし探索アルゴリズムなどの経路計画アルゴリズムを使用して、各経路５０を生成する。以下では、例として、経路計画アルゴリズムがメタヒューリスティックアルゴリズムとして実装されると仮定し、各経路５０を生成するために MOMAPF ソルバで使用するメタヒューリスティックアルゴリズムを「EA 経路プランナ」と呼ぶ。EA 経路プランナは、効用関数を使用して、それによって生成された経路５０の各候補に対する効用スコアを計算する。

＜作用効果の例＞
実施形態１の経路探索装置２０００によれば、車両集合１０内の複数の車両２０に対する競合のない経路を含む経路集合４０が生成される。経路探索装置２０００は、複数の目的が最適化される度合いをスカラー化する効用関数を使用するため、複数の目的の観点から最良の経路の集合を見出すことができる。したがって、パレート解のセット全体を提供する非特許文献２によって開示されている MO-CBS とは異なり、経路探索装置２０００は、複数のパレート最適な競合のない経路を提供する代わりに、最も高い効用を有する競合のない経路の単一セットを提供することができる。

経路探索装置２０００は、実用性及び効率性において MO-CBS よりも有利である。具体的には、経路探索装置２０００は、パレート最適解のセット全体を計算することなく、パレート最適解のセット全体のうちの１つである、又はそれに近い解を提供することができるので、 MO-CBS よりもはるかに少ない実行時間でオペレータなどに実用的な解を提供することができる。言い換えれば、経路探索装置２０００は、非特許文献２によって開示されているものよりも計算コストが小さい方法で解を提供することができる。加えて、経路探索装置２０００は、オペレータがパレート最適解のセット全体から最適解を選択することを必要とせず、それによって、オペレータが解を得るために要する時間と労力を削減する。さらに、オペレータが単一の最適解を知ることで十分であり、またパレート最適解のセット全体を知ることはオペレータにとって実用的ではない場合がある。

以下、経路探索装置２０００についてより詳細に説明する。

＜機能構成例＞
図２は、経路探索装置２０００の機能構成の一例を示す。経路探索装置２０００は、取得部２０２０及び MOMAPF 求解部２０４０を含む。取得部２０２０は、車両情報６０及び地図情報７０を取得する。MOMAPF 求解部２０４０は、地図情報７０により地図が定義され、車両情報６０により各車両２０の開始位置及び目標位置が定義された MOMAPF 問題を解き、車両集合１０用の経路集合４０を生成する。MOMAPF 問題は、MOMAPF ソルバを実行することによって解かれる。MOMAPF ソルバでは、各車両２０について、EA 経路プランナが呼び出されて車両２０の経路５０を生成する。EA 経路プランナでは、効用関数を使用して、複数の目的の観点から経路５０を評価する。

＜ハードウエア構成の例＞
経路探索装置２０００は、１つ以上のコンピュータで実現されうる。それら１つ以上のコンピュータのそれぞれは、経路探索装置２０００を実現するために作成された専用のコンピュータであってもよいし、パーソナルコンピュータ（PC: Personal Computer）、サーバマシン又はモバイルデバイスなどの汎用のコンピュータであってもよい。

経路探索装置２０００は、コンピュータにアプリケーションをインストールすることで実現されうる。そのアプリケーションは、コンピュータを経路探索装置２０００として機能させるプログラムで実現される。言い換えれば、そのプログラムは、経路探索装置２０００の機能構成部を実装したものである。

図３は、経路探索装置２０００を実現するコンピュータ１０００のハードウエア構成の一例を示すブロック図である。図３において、コンピュータ１０００は、バス１０２０、プロセッサ１０４０、メモリ１０６０、ストレージデバイス１０８０、入出力インタフェース１１００、及びネットワークインタフェース１１２０を有する。

バス１０２０は、プロセッサ１０４０、メモリ１０６０、ストレージデバイス１０８０、入出力インタフェース１１００、及びネットワークインタフェース１１２０が相互にデータの送信及び受信をするためのデータ通信路である。プロセッサ１０４０は、CPU（Central Processing Unit）、GPU（Graphics Processing Unit）、又は FPGA（Field-Programmable Gate Array）などといったプロセッサである。メモリ１０６０は、RAM（Random Access Memory）又は ROM（Read Only Memory）などの主記憶要素である。ストレージデバイス１０８０は、ハードディスク、SSD（Solid State Drive）、又はメモリカードなどの補助記憶要素である。入出力インタフェース１１００は、コンピュータ１０００と周辺デバイス（キーボード、マウス、又はディスプレイ装置など）との間のインタフェースである。ネットワークインタフェース１１２０は、コンピュータ１０００とネットワークとの間のインタフェースである。ネットワークは、LAN（Local Area Network）でもよいし、WAN（Wide Area Network）でもよい。

ストレージデバイス１０８０は、前述したプログラムを格納しうる。プロセッサ１０４０は、経路探索装置２０００の各機能構成部を実現するためにそのプログラムを実行する。

コンピュータ１０００のハードウエア構成は、図３に示される構成に限定されない。
例えば、前述したように、経路探索装置２０００は複数のコンピュータで実現されうる。この場合、それらのコンピュータは、ネットワークを介して互いに接続されうる。

＜処理のフロー＞
図４は、経路探索装置２０００が実行する処理の一例を示すフローチャートである。取得部２０２０は、車両情報６０及び地図情報７０を取得する（Ｓ１０２）。MOMAPF 求解部２０４０は、MOMAPF ソルバを実行し、地図情報７０が示す地図と、車両情報６０が示す車両２０の開始位置及び目標位置とで規定される MOMAPF 問題を解く（Ｓ１０４）。

＜車両情報６０の取得：Ｓ１０２＞
取得部２０２０は、車両情報６０を取得する（Ｓ１０２）。車両情報６０は、各車両の開始位置及び目標位置を示す。図５は、車両情報６０の構成例をテーブル形式で示す。図５の車両情報６０は、車両識別子２２、開始位置２４、及び目標位置２６のタプルを含む。各タプルは、その対応する車両の一組の開始位置と目標位置を示す。

車両情報６０を取得する方法は様々である。例えば、車両情報６０は、経路探索装置２０００がアクセス可能な記憶部に、その対応するエンティティの識別子と関連付けて予め記憶されている。この場合、取得部２０２０は、エンティティ３０の識別子に関連付けられた車両情報６０を記憶部から取得する。なお、取得部２０２０は、エンティティ３０の識別子を指定するユーザ入力を受け付けるなど、任意の手段でエンティティ３０の識別子を取得する。

別の実施例では、取得部２０２０は、エンティティ３０が操作するモバイル機器又は PC などの別のコンピュータから送信される車両情報６０を受信することによって車両情報６０を取得することができる。

＜地図情報７０の取得：Ｓ１０２＞
取得部２０２０は、地図情報７０を取得する（Ｓ１０２）。地図情報７０は、車両２０が移動する空間の地図を表す。理論的には、その地図は、グラフＧ＝（Ｖ，Ｅ）と表すことができる。ここで、Ｖは頂点の集合であり、Ｅはエッジの集合である。頂点は位置を表し、エッジは位置間の接続を表す。

MOMAPF 問題用の空間地図を実装する様々な方法がある。いくつかの実装形態では、地図は、二次元（２Ｄ）又は三次元（３Ｄ）のグリッドマップとして実装される。この場合、各位置は、グリッドマップ内のセルによって表される。さらに、位置間の各接続は、グリッドマップ内のセル間の接続によって表される。

地図情報７０はまた、壁、棚などの各静止障害物の位置を示すことができる。各障害物は、少なくとも車両２０の移動中に恒久的に占有される１つ以上の位置（例えば、グリッドマップのセル）によって定義される。

地図情報７０を取得するには様々な方法があってよい。例えば、地図情報７０は、経路探索装置２０００がアクセス可能な記憶部に予め記憶されている。この場合、取得部２０２０は、記憶部から地図情報７０を取得する。別の実施例では、取得部２０２０は、他のコンピュータから送られてくる地図情報７０を受信することにより取得してもよい。

＜MOMAPF 問題の求解：Ｓ１０４＞
MOMAPF 求解部２０４０は、MOMAPF ソルバを実行して、地図情報７０と車両情報６０とに基づいて定義される MOMAPF 問題を解き、車両集合１０用の経路集合４０を生成する。いくつかの実装形態では、MOMAPF ソルバは、コンフリクトベース探索（CBS）アルゴリズムの修正版によって実装される。なお、CBS のオリジナル版は、非特許文献１に開示されている。以下、経路探索装置２０００で採用される CBS の修正版を「修正 CBS 」と呼ぶ。

CBS は、高レベル探索と低レベル探索とに分けられる２レベルの探索アルゴリズムである。高レベル探索は、制約木（CT）と呼ばれる二進木を使用して実行される。CT の各ノードは、（１）その親ノードで実行された低レベル探索が検出した競合に関連する時間及び位置の制約、（２）そのノード及びその先祖が示すすべての制約を満たす単一候補解（すなわち、すべての車両の経路についての候補のセット）、及び（３）オリジナルの CBS 内のすべての車両の総経路持続時間の和である解の評価を、含む。CT のルートノードには、制約という空の集合を含む。

ノードに含まれる制約は、どの車両２０についてどの時刻におけるどの位置の占有を禁止するのか、を示す。例えば、時刻Ｔ１に、位置Ｌ１で車両Ａ１と車両Ａ２とが互いに競合したことが検出される。この場合、「車両Ａ１は、時刻Ｔ１に、位置Ｌ１を占有してはならない」という制約や、「車両Ａ２は、時間Ｔ１に、位置Ｌ１を占有してはならない」という制約を採用して、衝突を回避することができる。

CT の各ノードについて、経路５０が再計画されなければならない車両２０に対して低レベル探索が呼び出される。低レベル探索では、オリジナルの CBS が、経路計画アルゴリズムとしてＡ^＊探索アルゴリズムを使用して、現在のノード及びその先祖によって示される制約を満たしながら、車両の新たな経路を見つける。一方、修正 CBS は、低レベル探索における経路計画アルゴリズムとして EA 経路プランナ（すなわち、メタヒューリスティックアルゴリズム）を使用する。

以下、図６を参照して、CBS の全体的なフローについて説明する。図６は、CBS の全体のフローを示すフローチャートである。図６に示す全体的なフローは、オリジナルの CBS と修正 CBS との間で共通であることに留意されたい。まず、ルートノードを生成してオープンリストに追加することで、CT を初期化する（Ｓ２０２）。CT のノードを生成するステップは、（１）ノード及びその先祖によって示される制約の下でそのノードに対する候補解を生成するステップと、（２）その解を評価するステップを、含む。解及びその評価はノードに設定される。オープンリストには、候補解が競合なしであるか否かがチェックされるべき、１つ以上のノードを含む。

ルートノードを生成する場合、各車両の経路計画アルゴリズムを個別に呼び出して、各車両の経路を生成することによって、候補解が生成されることに留意されたい。一方、ルートノード以外のノードを生成する場合、候補解は、別の経路との競合により経路を再計画する必要がある単一の車両に対して、経路計画アルゴリズムを適用し、車両の古い経路を新たな経路に置き換えることによって、生成される。この新たな経路を除いて、このノードの候補解は親ノードの候補解と同じである。

競合のない解が見出されるまで、ステップＳ２０４～ステップＳ２０８が、繰り返される。ステップ２０４において、最良のノードがオープンリストから探索される。最良のノードは、最も高い評価を有するノードである。オリジナルの CBS の場合、コストが最も低いノードが最良のノードとして探索される。一方、後に詳述するように、修正 CBS は、最も高い効用を有するノードを最良のノードとして探索する。

探索されたノードは、その対応する候補解が競合なしであるか否かをチェックされる（Ｓ２０６）。探索されたノードに対応する候補解が競合なしである場合（Ｓ２０６：ＹＥＳ）、CBS は、この候補解を解決すべき MOMAPF 問題の解として出力した後に、終了する（Ｓ２１０）。

一方、探索されたノードに対応する候補解が競合なしでない場合（Ｓ２０６：ＮＯ）、探索されたノードの子ノードが生成され、オープンリストに追加される（Ｓ２０８）。

修正 CBS は、少なくとも以下の２点でオリジナルの CBS と異なる。まず、修正 CBS は、Ａ^＊探索アルゴリズムの代わりに、低レベル探索における経路計画アルゴリズムとして、EA 経路プランナを使用する。第二に、修正 CBS は、複数の目的の観点から候補解を評価する。Ａ^＊アルゴリズムの性質により、オリジナルの CBS は複数の目的を処理することができず、単一の目的（経路長）のみを処理する。一方、進化的アルゴリズムにはこの制限がないため、EA 経路プランナは複数の目的を処理することができる。

以下、これら２点についてより詳細に説明する。

＜＜低レベル探索用の進化的アルゴリズム＞＞
上述したように、修正 CBS では、低レベル探索用の経路計画アルゴリズムは、EA 経路プランナによって実装される。いくつかの実装形態では、EA 経路プランナは進化的アルゴリズムに属する遺伝的アルゴリズム（Genetic Algorithm）によって実装される。以下では、遺伝的アルゴリズムによって実装され、修正 CBS において低レベル探索に採用されている EA 経路プランナを、「GA 経路プランナ」と呼ぶ。

図７は、MOMAPF 求解部２０４０が実行する GA 経路プランナの一例のフローを示すフローチャートである。上述したように、低レベル探索は、そのノード及びその先祖によって示される制約の下で、CT のノードにおいて車両２０に対して実行されることに留意されたい。以下、GA 経路プランナが呼び出された車両２０を「対象車両」と呼ぶ。

まず、GA 経路プランナは、CT の現在のノード及びその先祖に対応する制約の下で、対象車両の候補経路の初期母集団を生成する（Ｓ３０２）。一般的な GA アルゴリズムでは、「母集団」という用語は、候補解の集合を意味する。GA 経路プランナの場合、母集団は対象車両の候補経路の集合（すなわち、経路５０の候補）を表す。母集団は、対象車両の開始位置から目標位置までの経路である複数の候補経路をランダムに生成することによって初期化される。

ステップＳ３０４～Ｓ３１２は、ステップＳ３０６において、予め定義された終了条件が満たされたと判定されるまで繰り返し実行される。終了条件については後述する。

Ｓ３０４において、GA 経路プランナは効用関数を使用して母集団内の各候補経路を評価する。そして、GA 経路プランナは、終了条件が満たされているか否かをチェックする（Ｓ３０６）。終了条件が満たされている場合（Ｓ３０６：ＹＥＳ）、GA 経路プランナは、現在の母集団において最も効用が高い候補経路を出力し（Ｓ３１４）、その後終了する。

終了条件を満たさない場合（Ｓ３０６：ＮＯ）、GA 経路プランナは、母集団を次世代に変換するために、遺伝的演算子（選択、交差及び変異）を母集団に適用する。ステップＳ３０８において、GA 経路プランナは母集団から生存者を選択する。生存者は、母集団に保持される候補経路である。換言すれば、母集団の残りの部分（すなわち、生存者以外の候補経路）が母集団から削除される。GA アルゴリズムにおける生存者を選択するには様々な周知の方法、例えば、ランダム選択があり、それらのうちのいずれか１つを使用することができる。

次に、GA 経路プランナは、母集団内の１つ以上の候補経路を交差で修正して新たな候補経路を生成し、生成した候補経路を母集団に追加する（Ｓ３１０）。そして、GA 経路プランナは、変異を持つ母集団の１つ以上の候補経路を修正して新たな候補経路を生成し、生成した候補経路を母集団に追加する（Ｓ３１２）。これら組み換えの詳細については後述する。なお、変異による組み換えは、交差による組み換えの前に実行してもよい。

遺伝的演算子を母集団に適用した後、GA 経路プランナはステップＳ３０４：母集団の評価に戻る。このようにすることで、終了条件が満たされるまで、母集団の次世代への変換と、母集団の評価とが繰り返し実行される。

GA 経路プランナには様々な終了条件を採用することができる。例えば、終了条件には、「反復回数が予め定義された閾値に達する」という条件を含んでもよい。この場合、GA 経路プランナは、予め定義された回数を超えてステップＳ３０６を実行すると、終了する。

これに代えて、又はこれに加えて、終了条件には、「適応度レベルの変化が、所与の反復回数に対して予め定義された閾値未満である」という条件を含んでもよい。これは、GA 経路プランナが収束するまで実行されることを意味する。GA アルゴリズムでは、適応度レベルは、現在の解が所与の問題の最適解にどれくらい近いかを表す。GA 経路プランナでは、各反復において、母集団内の候補経路に対して計算されたものの最高の効用スコアを適応度レベルの値として使用することができる。

以下、交差及び変異による組み換えについてより詳細に説明する。

＜＜＜交差による組み換え＞＞＞
交差のステップは、主に、より良い候補経路を取得するために世代を改良する役割を果たす。この改良は、両親と呼ばれる２つ以上の個体（母集団内の経路候補）を組み換えて、子孫と呼ばれるより良い解を生成することによって達成される。

GA 経路プランナの背景には、交差ステップが、２つの親候補経路、すなわち選択ステップ後の生存者を、新たな子孫経路に結合することを含む。図８は、交差ステップの一例を示す。候補経路８０－１及び８０－２は、２つの共通位置９０－１及び９０－２を有する。候補経路８０－１及び候補経路８０－２に交差による組み換えを適用し、それにより候補経路８０－３及び候補経路８０－４を生成する。具体的には、候補経路８０－３及び８０－４は、位置９０－１と位置９０－２との間の候補経路８０－１の部分を、位置９０－１と位置９０－２との間の候補経路８０－２の部分と交換することによって生成される。

交差ステップが適用される候補経路は、その中に少なくとも１つの共通位置を有する必要がある。したがって、GA 経路プランナは、少なくとも１つの共通位置を有する２つの候補経路の１つ以上の組について母集団を探索し、見出された１つ以上の組に交差ステップを適用することができる。

＜＜＜変異を伴う組み換え＞＞＞
変異ステップは、必要な多様性を与え、解空間を探索し、母集団が局所最適値に留まるのを防ぐためにある。GA 経路プランナでは、可能性としてより良い解を探索するために、１つ以上の種類の変異移動が使用される。例えば、GA 経路プランナは、ランダムな移動又は通知された移動を実行することにより、候補経路の一部を修正する。ランダム移動の場合、GA 経路プランナは候補経路の１つ以上の部分をランダムに選択し、選択された部分をランダムな手段で修正する。

より具体的には、GA 経路プランナは、最も早い競合の前に位置するウェイポイントを、ランダムに選択する。ウェイポイントは、経路内の単一のポイントが記述される位置及び時間のセットであることに留意されたい。次に、ランダムに選択されたウェイポイントの近傍における可能な組み換えのセットが決定され、それらの中から１つの移動がランダムに選択される。２つの種類の可能な組み換え、迂回及び待機移動があり得る。迂回は、経路の一部を空間的に修正する組み換えである。待機移動は、その位置がランダムに選択されたウェイポイントの位置と同じであり、その時間がランダムに選択されたウェイポイントの時間とは異なる、新たなウェイポイントを追加し、それによってその経路にさらに１つの時間のステップを追加する組み換えである。GA 経路プランナは、２つ以上のウェイポイントをランダムに選択し、ランダムに選択されたウェイポイントのそれぞれに対して１つの移動を実行することができることに、留意されたい。

組み換え後の経路が実行不可能である場合、実行可能な解が見出されるまで選択が繰り返される。可能な組み換えのセットが実行可能な移動を含まない場合、そのセットは、選択されたウェイポイント周り付近の迂回及び待機時間のステップが増加するという意味において、増分する。

通知される移動に関して、GA 経路プランナは、予め定義された条件を満たす候補経路の１つ以上の部分を検出し、検出された部分を予め定義された方法で修正する。いくつかの実装形態では、通知される移動には、１つ以上のウェイポイントの削除を含むことができる。ウェイポイントの削除を実行する場合、GA 経路プランナは、迂回を形成するウェイポイントを検出し、それらのウェイポイントを削除して候補経路から迂回を除去する。図９は、変異の候補経路からのウェイポイントの削除を示す。簡単にするために、図９は、車両が方向を変えるウェイポイントのみを示している。図９の上の図において、候補経路８０－５は、迂回を形成するウェイポイント１００－１、ウェイポイント１００－２、ウェイポイント１００－３、及びウェイポイント１００－４を含む。この例では、ウェイポイント１００－１～ウェイポイント１００－４を削除することによって、新たな候補経路８０－６が生成される。車両が方向を変えるウェイポイントを削除することによって、候補経路内の曲がり角の数が減少し、したがって、候補経路の平滑性が増加する。

図９の下の図では、候補経路８０－７は、迂回を形成するウェイポイント１００－５、ウェイポイント１００－６、及びウェイポイント１００－７を含む。この例では、ウェイポイント１００－１～ウェイポイント１００－３を削除することによって新たな候補経路８０－８が生成される。

他の実装形態では、通知される移動には、ウェイポイントの追加を含むことができる。ウェイポイントの追加は、対象車両以外の車両の経路との競合を解決するために実施することができる。具体的には、GA 経路プランナは、対象車両以外の車両の経路と競合する候補経路の１つ以上の部分を検出する。次に、GA 経路プランナは、衝突を回避するために候補経路にウェイポイントを追加する。

経路にウェイポイントを追加する方法には少なくとも２つ、空間におけるウェイポイントを追加する方法、及び時間におけるウェイポイントを追加する方法がある。図１０及び図１１は、変異に対する候補経路への１つ以上のウェイポイントの追加を示す。図１０において、候補経路８０－９は、その方向が候補経路８０－９と逆向きである経路１３０－１と競合するエッジを有する。エッジ競合は、２台の車両が反対方向から同じエッジを通って移動する競合の一種である。

GA 経路プランナは、エッジ競合の位置の周りにウェイポイントをランダムに追加し、それによって候補経路８０－９に迂回を追加して、経路１３０－１とのエッジ競合を解決することができる。具体的には、４つのウェイポイント１００－８、ウェイポイント１００－９、ウェイポイント１００－１０、及びウェイポイント１００－１１が候補経路８０－９に追加され、それによって候補経路８０－１０を生成する。

図１１においては、候補経路８０－１１は、時刻Ｔ１に位置Ｌ１において経路１３０－２と競合する頂点を有する。頂点競合は、２台の車両が同時に同じ位置を占める競合の一種である。頂点競合は、他方の車両が衝突が発生する位置を通過するまで、一方の車両が待機する場合に、解決することができる。

したがって、図１１の場合、GA 経路プランナは、頂点競合の位置の前に位置し、別の既存の車両と競合しない、いくつかのランダムな位置にウェイポイントをランダムに追加することができる。図１１では、GA 経路プランナは２つのウェイポイント１００－１２及びウェイポイント１００－１３を候補経路８０－１１に追加し、それによって候補経路８０－１２を生成することができる。ウェイポイント１００－１２は（位置Ｌ２、時刻Ｔ２）を示し、一方、ウェイポイント１００－１３は（位置Ｌ２、時刻Ｔ３）を示し、ここでＴ２＜Ｔ１＜Ｔ３である。同じ位置であるが異なる時間を示す２つのウェイポイントを追加することによって、待機動作が候補経路に追加される。図１１の場合、対象車両は、時刻Ｔ２～時刻Ｔ３において位置Ｌ２に留まるようスケジュールされる。したがって、経路１３０－２に沿って移動する車両は、対象車両が位置Ｌ２に留まっている間に位置Ｌ１を通過する。その結果、頂点競合が解決する。

＜＜候補経路の評価＞＞
GA 経路プランナの実行中、母集団内の各候補経路は、複数の目的の観点から評価される。具体的には、候補経路は、候補経路の効用スコアを計算する効用関数を使用して評価される。効用スコアは、複数の目的が最適化される度合いを表すスカラー値である。このように、複数の目的の観点から、効用関数によって、候補経路の効用が効用スコアとしてスカラー化される。

考えられ得る様々な目的がある。目的のいくつかの例は、（１）効率性、（２）安全性、及び（３）平滑性である。候補経路の効率性は、候補経路の全長として定義することができる。具体的には、候補経路の全長が短いほど、候補経路がより効率的であると評価される。この場合、候補経路の効率性は、以下のように計算することができる。
式中、ef(P) は経路Ｐの効率性を表し、x_i は経路Ｐにおけるｉ番目の位置を表し、d(A,B) は位置Ａと位置Ｂとの間の距離を表す。

候補経路の安全性は、対象車両の経路と障害物との間の最短距離として定義することができる。具体的には、対象車両と障害物との最短距離が長いほど、経路はより安全であると評価される。この場合、候補経路の安全性は、以下のように計算することができる。
式中、sa(P) は経路Ｐの安全性を表し、d(A,B) はＡとＢとの間の距離を表し、上線は２つの位置の間の線分を表し、そして Oj はｊ番目の障害物を表す。

別の例では、候補経路の安全性は、以下のように計算することができる。

候補経路の平滑性は、候補経路に沿った移動中の角度の変化平均として定義することができる。具体的には、候補経路における角度の変化平均が小さいほど、候補経路がより平滑であると評価される。候補経路の平滑性は、以下のように計算することができる。
式中、sm(P) ｓは候補経路Ｐの平滑性を表し、x_i は、候補経路Ｐ内のｉ番目の位置であり、angle(A,B,C)は、線ＢＡと線ＢＣとの間の角度であり、N は、式（４）で合計された角度の数、すなわち、候補経路Ｐ内のウェイポイントの数から２を引いた数を表す。

別の例では、候補経路の平滑性は、曲がり角の数として定義してもよい。この場合、候補経路の平滑性は、以下のように計算することができる。

上述したように、候補経路の効用は、効用スコアと呼ばれるスカラー値を出力する効用関数を使用して計算される。例えば、効用関数は、複数の目的項の重み付きの和として定義され、各目的項は、その対応する目的が最適化される度合いを表す。この場合、効用関数は、以下のように定義することができる。
式中、u(P) は候補経路Ｐの効用スコアを表し、ｉは目的の識別子を表し、w_i は、ｉ番目の目的に割り当てられた重みを表し、f_i() は、ｉ番目の目的の観点からの候補経路Ｐの効用を表すスカラー値を出力する関数を表し、n_i は正規化係数を表し、そして N は目的の数を表す。

効率性、安全性、及び平滑性を目的として使用する場合、効用関数は以下のように定義することができる。
式中、n_ef、n_sa、及び n_sm は、それぞれ効率性、安全性、及び平滑性の正規化係数を表す。

各目的に割り当てられる重みは、予め人手で定義してもよい。しかしながら、後で詳細に説明するように、目的の重みは、ユーザの好みに基づいて経路探索装置２０００によって動的に決定することができる。

上記の説明では、上記で説明した効率性、安全性、及び平滑性は、それらの値が小さいほど良好であることに留意されたい。したがって、効用スコア u(P) が小さいほど、候補経路Ｐの効用がより高いと評価される。したがって、GA 経路プランナは、最も低い効用スコアを有する候補経路を最も高い効用を有する候補経路として選択する。

考慮されるべき目的は、経路の効率性、安全性、及び平滑性に限定されないことにも留意されたい。例えば、車両のエネルギー消費又は車両のタスク割り当てを目的として扱うことができる。

経路の効用は、複数の目的の重み付きの和に限定されないことにも留意されたい。複数の目的の最適化の度合いを考慮して単一のスカラー値を計算することができる任意の方法を採用することができる。例えば、チェビシェフ法を採用することができる。

図６のステップ２０４において最良のノードを決定するために、MOMAPF ソルバは、各ノードについて経路集合４０の候補の効用を評価する。経路集合４０の候補の効用は、候補内の各経路の効用スコアに基づいて計算することができる。例えば、MOMAPF ソルバは、経路集合内のすべての経路の効用スコアの和として、経路集合の効用スコアを計算する。別の実施例では、MOMAPF ソルバは、経路集合内のすべての経路の効用スコアの統計値（例えば、平均値、最小値、最大値など）として経路の効用スコアを計算する。

効用スコアが小さいほど経路の効用が高い場合、経路の効用スコアが小さいほど経路集合の効用が高い。したがって、MOMAPF ソルバによって最良のノードとして選択されたノードは、その効用スコアがすべての中で最も小さい経路集合の候補を含む。

＜結果の出力＞
MOMAPF 求解部２０４０は、MOMAPF ソルバが解く MOMAPF 問題の解として、経路集合４０を取得する。経路探索装置２０００は、経路集合４０を示す情報（以下、出力情報）を出力することができる。出力情報を出力するには、様々な方法がある。いくつかの実装形態では、経路探索装置２０００は、出力情報を記憶装置に格納することができる。他の実装形態では、経路探索装置２０００は、ディスプレイ装置が出力情報を表示するように、出力情報をディスプレイ装置に出力することができる。この場合、ディスプレイ装置は、地図情報７０が示す地図、車両情報６０が示す各車両２０の開始位置及び目標位置、及び経路集合４０に含まれる各車両２０の経路５０を表示することができる。他の実装形態では、経路探索装置２０００は、何らかの方法で経路集合を使用する任意のコンピュータに出力情報を送信することができる。

実施形態２
＜概要＞
図１２は、実施形態２の経路探索装置２０００の概要を示す。なお、図１２に示す概要は、経路探索装置２０００を分かりやすくするために経路探索装置２０００の動作の一実装例を示したものであり、経路探索装置２０００が取り得る動作の範囲を限定したり狭めたりするものではない。

実施形態２の経路探索装置２０００は、例えば、効用関数（例えば、重み付きの和として定義される効用関数における目的の適切な重み）において考慮される各目的の重要性に関してユーザの好みを引き出し、その構成がユーザの好みに基づいて決定される新たな効用関数を生成することを除いて、実施形態１の経路探索装置と同じである。

効用関数の具体的な構成方法は、効用関数の種類に依存する。例えば、効用関数が複数の目的の重み付きの和として定義される場合、効用関数の構成は目的の重みの集合である。なお、実施形態１において、効用関数の構成は、予め定義されていてもよい。

具体的には、実施形態２の経路探索装置２０００は、適切な効用関数が見出されるまで、効用関数を更新しながら MOMAPF 問題を繰り返し解く。各反復において、経路探索装置２０００は、互いに異なる構成を有する効用関数を使用して MOMAPF ソルバによって生成された経路集合４０の複数の候補をユーザに提供し、ユーザに候補のうちの１つを選択させ、選択された候補が生成された効用関数の構成に基づいてその構成が決定される新たな効用関数を生成する。

＜作用効果の例＞
経路探索装置２０００は、効用関数を使用して計算された経路の効用スコアを使用して経路集合４０の候補を評価するため、評価の精度は効用関数の構成に依存する。具体的には、効用関数がより適切に構成されるほど、効用スコアは経路の効用をより正確に表す。しかしながら、効用関数の適切な構成をユーザが自ら把握することは困難な場合がある。

実施形態２の経路探索装置２０００によれば、複数の候補からの経路集合のユーザ選択に基づいて、効用関数が繰り返し修正され、それによって効用関数を改善する。したがって、経路探索装置２０００は、経路の効用を正確に計算することができる効用関数を自動的に生成することができる。その結果、経路探索装置２０００は、経路集合４０に高い効用を正確に与えることができる。

以下、経路探索装置２０００についてより詳細に説明する。

＜機能構成例＞
図１３は、実施形態２に係る経路探索装置２０００の機能構成の一例を示すブロック図である。実施形態２の経路探索装置２０００は、実施形態１の経路探索装置２０００と比較して、候補提供部２０６０及び嗜好誘出部２０８０をさらに含む。候補提供部２０６０は、MOMAPF 問題の解として取得された２つ以上の経路集合４０の候補を、異なる効用関数を使用して、選択可能な手段で、ユーザに提供する。嗜好誘出部２０８０は、ユーザがどの経路集合４０の候補を選択したかを示す情報を取得し、ユーザの選択に基づいて新たな効用関数を生成する。

次に、MOMAPF 求解部２０４０が、新たな効用関数を用いて MOMAPF ソルバを計算する。そして、候補提供部２０６０は、新たな効用関数を使用して生成された経路集合４０の候補を、ユーザが最後に選択した経路集合４０の候補とともにユーザに提供する。予め定義された終了条件が満たされるまで、経路探索装置２０００は、経路集合４０の複数の候補を選択可能な手段で提供し、経路集合４０の候補のユーザ選択に基づいて、新たな効用関数を生成しながら、経路集合４０の候補を繰り返し生成する。

＜ハードウェア構成例＞
実施形態２の経路探索装置２０００は、実施形態１の経路探索装置２０００を実現するものと同様の１つ以上のコンピュータによって実現することができる。したがって、そのハードウェア構成も図３により示すことができる。

＜処理のフロー＞
図１４は、実施形態２における経路探索装置２０００が実行する処理の一例を示すフローチャートである。実施形態２の取得部２０２０は、実施形態１と同様の手段で、車両情報６０及び地図情報７０を取得する（Ｓ４０２）。MOMAPF求解部２０４０は、構成が互いに異なる複数の効用関数を初期化する（Ｓ４０４）。

ステップＳ４０６～ステップＳ４１４は、予め定義された終了条件が満たされるまで繰り返し実行される。MOMAPF 求解部２０４０は、MOMAPF ソルバを実行する（Ｓ４０６）。最初の反復では、ステップＳ４０４で初期化された複数の効用関数の各々について、MOMAPF ソルバが実行される。一方、２回目以降の反復では、前回のステップＳ４１２で生成された効用関数に対して MOMAPF ソルバが実行される。

候補提供部２０６０は、経路集合４０の２つ以上の候補を提供し（Ｓ４０８）、ユーザの選択を取得する（Ｓ４１０）。嗜好誘出部２０８０は、取得した選択に基づいて、新たな効用関数を生成する（Ｓ４１２）。

嗜好誘出部２０８０は、終了条件を満たすか否かをチェックする（Ｓ４１４）。終了条件を満たす場合（Ｓ４１４：ＹＥＳ）、経路探索装置２０００は、ユーザの最新の選択である経路集合４０を出力する（Ｓ４１６）。

一方、終了条件が満たされていない場合には（Ｓ４１４：ＮＯ）、MOMAPF 求解部２０４０は、新たな効用関数を用いた MOMAPF ソルバを実行する（Ｓ４０６）。

＜効用関数の初期化：Ｓ４０４＞
MOMAPF 求解部２０４０は、複数の効用関数を初期化する（Ｓ４０４）。本ステップにおいて、MOMAPF 求解部２０４０は、互いに異なる構成を有する複数の効用関数を生成する。上記式（７）によって効用関数が定義され、初期化ステップにおいて２つの効用関数が生成されたとする。この場合、MOMAPF 求解部２０４０は、２つの効用関数、「w_1=a，w_2=b，w_3=c」の構成を伴う u_1(P)、及び「w_1=d，w_2=e，w_3=f」の構成を伴う u_2(P) を生成することができ、ここで a、b、c、d、e、f の値は０以上の実数であり、a+b+c=1、及び d+e+f=1 である。

効用関数を初期化するには、様々な方法がある。いくつかの実装形態では、効用関数はランダムな方法で生成される、例えば、各目的の重みがランダムに決定される。

＜MOMAPF ソルバの実行：Ｓ４０６＞
MOMAPF 求解部２０４０は、MOMAPF ソルバを実行して経路集合４０の候補を生成する（Ｓ４０６）。最初の反復（すなわち、効用関数の初期化直後）では、MOMAPF 求解部２０４０は、初期化ステップで生成された複数の効用関数の各々について MOMAPF ソルバを実行する。特定の効用関数を用いて MOMAPF ソルバを実行する場合、この効用関数を用いて、MOMAPF ソルバにおける候補経路を評価する。

２回目以降の反復では、直近のステップＳ４１２で生成された新たな効用関数を用いて MOMAPF ソルバが実行される。したがって、候補経路は、新たな効用関数を使用して評価される。

複数の MOMAPF 問題を解決することは時間がかかる可能性があるため、ユーザは MOMAPF ソルバの複数の実行を待ちたくない場合があることに留意されたい。したがって、いくつかの実装形態では、車両情報６０及び地図情報７０を取得した後、経路探索装置は、ユーザの好みの誘出と同期することなくユーザに提案できる可能な効用関数の各々について MOMAPF 問題の解を計算することができる。そうすることによって、MOMAPF 問題の解は、予め可能な効用関数の各々について準備することができる。

したがって、MOMAPF ソルバが新たな効用関数で実行される場合、MOMAPF ソルバは、新たな効用関数に対応する解が既に用意されているか否かをまず判定することができる。解が用意されている場合、MOMAPF ソルバは、その時点で MOMAPF 問題の解を出すことなく、用意された解が記憶されている記憶装置からそれを取り出すことによって、準備された解を提供する。一方、解がまだ用意されていない場合、MOMAPF ソルバは、新たな効用関数を使用して MOMAPF 問題の解を出し、解を提供する。

＜候補経路集合の提供：Ｓ４０８＞
候補提供部２０６０は、異なる効用関数を使用して生成された複数の経路集合４０の候補を提供する（Ｓ４０８）。最初の反復では、MOMAPF 求解部２０４０は、構成の異なる効用関数を使用して MOMAPF ソルバを実行し、それにより経路集合４０の複数の候補を得る。候補提供部２０６０は、これら複数の候補をユーザが互いに比較できるようにユーザに提供することができる。

２回目以降の反復では、MOMAPF 求解部２０４０は、直近のステップ４１２で生成された新たな効用関数を使用して MOMAPF ソルバを実行し、それにより経路集合４０の新たな候補を得る。次いで、ユーザに提供されるべき経路集合４０の複数の候補は、前の反復においてユーザによって選択されなかった経路集合４０の候補を、現在の反復において生成された経路集合４０の新たな候補で置き換えることによって修正される。これにより、候補提供部２０６０は、前回の反復で選択された経路集合４０の候補とともに、現在の反復で生成された経路集合４０の新たな候補をユーザに提供するので、ユーザは、新たな候補と、先に選択された候補とを比較することができる。

候補提供部２０６０は、ユーザが容易に互いを比較できるように、経路集合４０の複数の候補を視覚的に提供することが好ましい。図１５は、経路集合４０の複数の候補の視覚的な提供を示す。ウィンドウ１１０は、ユーザが見ることができるディスプレイ装置、例えば、ユーザのモバイル機器や PC などのディスプレイ装置に表示することができるウィンドウである。図１５において、効用関数は、効率性、安全性、及び平滑性の重み付きの和である式（７）で定義されるものとする。

ウィンドウ１１０は、経路集合４０の２つの候補を視覚的に示す。左側の候補は、「効率性（EF）、安全性（SA）、及び平滑性（SM）の重みがそれぞれ a1、b1、及び c1 である」構成の効用関数を使用して生成される。右側の候補は、「効率性（EF）、安全性（SA）、及び平滑性（SM）の重みがそれぞれ a2、b2、及び c2 である」構成の効用関数を使用して生成される。ウィンドウ１１０にはまた、総移動時間（経路集合４０の効率性）、安全度、及び平滑度も表示されており、ユーザは、これらの値を考慮しながら、経路集合４０の候補のいずれかを選択することができる。

入力インタフェース１２０は２つのボタンを含み、左側のボタンは構成１を選択するのに使用し、右側のボタンは構成２を選択するのに使用する。ユーザは、その対応するボタンを押すことにより、経路集合４０の候補のいずれかを選択することができる。

＜ユーザ選択の取得：Ｓ４１０＞
嗜好誘出部２０８０は、ユーザの選択を取得する（Ｓ４１０）。どのオプションをユーザが選択したかを取得する様々な方法がある。例えば、図１５に例示する場合では、嗜好誘出部２０８０は、ユーザがどのボタンを押下したかを示す情報を取得する。

＜効用関数の生成：Ｓ４１２＞
嗜好誘出部２０８０は、ユーザによる経路集合４０の候補の選択に基づいて、新たな効用関数を生成する。具体的には、嗜好誘出部２０８０は、ユーザによる経路集合４０の候補の選択に基づいて、効用関数の新たな構成を決定し、決定した構成の効用関数を生成する。

経路集合４０の候補についてのユーザの選択に基づいて、効用関数の構成を決定するには様々な方法がある。いくつかの実装形態では、嗜好誘出部２０８０は、ベイズ最適化を使用して効用関数の構成を決定する。例えば、非特許文献３又は非特許文献４に開示されているガウス過程によるベイズ最適化を用いてもよい。より正確には、ガウスプロビットモデル（非特許文献３及び非特許文献４）を優先度学習に使用することができる。この場合、嗜好誘出部２０８０は、現在の反復のステップＳ４１０でユーザが選択した経路集合４０の候補の生成に使用した効用関数の構成を取得し、取得した効用関数の構成を入力として使用するガウス過程によるベイズ最適化を実行する。そして、嗜好誘出部２０８０は、ベイズ最適化の出力として効用関数の新たな構成を取得し、取得した新たな構成を用いて新たな効用関数を生成する。ガウス過程によるベイズ最適化では、Matern カーネルが一般的に使用される。しかしながら、どのような種類のカーネルが嗜好誘出部２０８０によって使用されてもよい。また、一般的に使用することができる取得関数（acquisition function）は、Upper Confidence Bound である。

＜嗜好誘出の終了：Ｓ４１４＞
経路探索装置２０００は、終了条件が満たされた場合、経路集合４０を出力する。終了条件に含めることができる条件には様々なものがある。例えば、終了条件には、「反復回数が予め定義された閾値に達する」という条件を含んでもよい。この場合、経路探索装置２０００は、ステップＳ４１４が予め定義された回数を超えた場合、経路集合４０を出力する。

これに代えて、又はこれに加えて、終了条件には、「生成モデルが収束に達する」という条件を含めることができる。なお、生成モデルが収束に達するか否かを判定する公知の様々な手法があり、そのうちの１つの手法を使用して生成モデルが収束に達したか否かを判定することができる。

＜結果の出力＞
終了条件が満たされた後（Ｓ４１４：ＹＥＳ）、経路探索装置２０００は、ユーザの最新の選択肢である経路集合４０の候補を経路集合４０として示す、出力情報を出力する。出力情報の出力方法については、実施形態１で既に説明した。

実施の形態を参照して本開示を説明したが、本開示は上述の実施の形態に限定されるものではない。本開示の構成や詳細には、本開示のスコープ内で当業者が理解し得る様々な変更をすることができる。

本開示におけるプログラムは、コンピュータに読み込まれた場合に、実施形態で説明された１又はそれ以上の機能をコンピュータに行わせるための命令群（又はソフトウェアコード）を含む。プログラムは、非一時的なコンピュータ可読媒体又は実体のある記憶媒体に格納されてもよい。限定ではなく例として、コンピュータ可読媒体又は実体のある記憶媒体は、random-access memory（RAM）、read-only memory（ROM）、フラッシュメモリ、solid-state drive（SSD）又はその他のメモリ技術、CD-ROM、digital versatile disc（DVD）、Blu-ray（登録商標）ディスク又はその他の光ディスクストレージ、磁気カセット、磁気テープ、磁気ディスクストレージ又はその他の磁気ストレージデバイスを含む。プログラムは、一時的なコンピュータ可読媒体又は通信媒体上で送信されてもよい。限定ではなく例として、一時的なコンピュータ可読媒体又は通信媒体は、電気的、光学的、音響的、またはその他の形式の伝搬信号を含む。

上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
＜付記＞
（付記１）
経路探索装置であって、
少なくとも１つのプロセッサと、
命令を記憶するメモリと、を備え、
前記少なくとも１つのプロセッサは、前記命令を実行して、
車両情報及び地図情報を取得し、前記車両情報は複数の車両の各々について開始位置と目標位置の組を示し、前記地図情報は前記車両が移動する空間の地図を示し、
前記車両情報と前記地図情報とを使用して、前記車両の各々について経路を含む経路集合を決定し、前記経路集合の前記経路は互いに競合しないように構成され、
前記経路集合の前記決定は、経路計画アルゴリズムを実行して前記車両の各々について前記経路を生成することを含み、前記経路計画アルゴリズムは、複数の目的が前記経路によって最適化される度合いを表すスカラー値である前記経路の効用スコアに基づいて、前記経路を評価する、経路探索装置。
（付記２）
前記経路集合の前記決定は、メタヒューリスティックアルゴリズムによって実装される前記経路計画アルゴリズムを実行することによって低レベル探索が実行される、コンフリクトベース探索アルゴリズムの修正版を実行することを含む、
付記１に記載の経路探索装置。
（付記３）
前記経路計画アルゴリズムは、効用関数を使用して前記対象経路の前記効用スコアを計算し、
前記効用関数は、複数の目的項の重み付き和として定義され、各前記目的項は、その目的項に対応する前記目的が前記経路によって最適化される度合いを表す、
付記１又は付記２に記載の経路探索装置。
（付記４）
前記複数の目的は、前記経路の効率性、前記経路の安全性、前記経路の平滑性、又はそれらの２つ以上を含む、
付記３に記載の経路探索装置。
（付記５）
前記経路計画アルゴリズムは、効用関数を使用して前記対象経路の前記効用スコアを計算し、
前記経路集合の前記決定は、
選択可能な手段で前記経路集合の複数の候補をユーザに提供することと、
前記ユーザが選択した前記経路集合の前記候補を示す情報を取得することと、
前記経路集合の前記選択された候補に基づいて新たな効用関数を生成することと、
前記新たな効用関数を使用して前記経路集合の新たな候補を決定することと、
前記ユーザに提供すべき前記経路集合の前記複数の候補のうちの１つを、前記経路集合の前記新たな候補に置き換えることと、
を、終了条件が満たされるまで繰り返し実行することを含む、付記１から付記４のいずれか一項に記載の経路探索装置。
（付記６）
前記新たな効用関数の前記生成は、
前記ユーザが最後に選択した前記経路集合の前記候補を生成するのに使用された前記効用関数の構成を入力として使用するガウス過程によるベイズ最適化を実行し、それによって前記効用関数の新たな構成を取得することと、
前記取得された新たな構成を用いて前記新たな効用関数を生成することと、
をさらに含む、付記５に記載の経路探索装置。
（付記７）
車両情報と地図情報を取得することを含み、前記車両情報は複数の車両の各々について開始位置と目標位置の組を示し、前記地図情報は前記車両が移動する空間の地図を示し、
前記車両情報と前記地図情報を使用する前記車両の各々についての経路を含む経路集合を決定することを含み、前記経路集合の前記経路は互いに競合せず、
前記経路集合の前記決定は、経路計画アルゴリズムを実行して、前記車両の各々について前記経路を生成することを含み、前記経路計画アルゴリズムは複数の目的が前記経路によって最適化される度合いを表すスカラー値である前記経路の効用スコアに基づいて、前記経路を評価する、
コンピュータにより実行される制御方法。
（付記８）
前記経路集合の前記決定は、メタヒューリスティックアルゴリズムが実装する前記経路計画アルゴリズムを実行することによって、低レベル探索を実行するコンフリクトベース探索アルゴリズムの修正版を実行することを含む、
付記７に記載の制御方法。
（付記９）
前記経路計画アルゴリズムは、効用関数を使用して前記対象経路の前記効用スコアを計算し、
前記効用関数は、複数の目的項の重み付き和として定義され、各前記目的項は、その目的項に対応する前記目的が前記経路によって最適化される度合いを表す、
付記７又は付記８に記載の制御方法。
（付記１０）
前記複数の目的は、前記経路の効率性、前記経路の安全性、前記経路の平滑性、又はそれらの２つ以上を含む、
付記９に記載の制御方法。
（付記１１）
前記経路計画アルゴリズムは、効用関数を使用して前記対象経路の前記効用スコアを計算し、
前記経路集合の前記決定は、
選択可能な手段で前記経路集合の複数の候補をユーザに提供することと、
前記ユーザが選択した前記経路集合の前記候補を示す情報を取得することと、
前記経路集合の前記選択された候補に基づいて新たな効用関数を生成することと、
前記新たな効用関数を使用して前記経路集合の新たな候補を決定することと、
前記ユーザに提供すべき前記経路集合の前記複数の候補のうちの１つを、前記経路集合の前記新たな候補に置き換えることと、
を、終了条件が満たされるまで繰り返し実行することを含む、付記７から付記１０のいずれか一項に記載の制御方法。
（付記１２）
前記新たな効用関数の前記生成は、
前記ユーザが最後に選択した前記経路集合の前記候補を生成するのに使用される前記効用関数の構成を入力として使用するガウス過程によるベイズ最適化を実行し、それによって前記効用関数の新たな構成を取得することと、
前記取得した新たな構成を用いて前記新たな効用関数を生成することと、
をさらに含む、付記１１に記載の制御方法。
（付記１３）
コンピュータに、
車両情報と地図情報を取得することを実行させ、前記車両情報は複数の車両の各々について開始位置と目標位置の組を示し、前記地図情報は前記車両が移動する空間の地図を示し、
前記車両情報と前記地図情報を使用して、前記車両の各々について経路を含む経路集合を決定することを実行させ、前記経路集合の前記経路は互いに競合せず、
前記経路集合の前記決定は、経路計画アルゴリズムを実行して前記車両の各々について前記経路を生成することを含み、前記経路計画アルゴリズムは、前記経路によって複数の目的が達成される度合いを表すスカラー値である前記経路の効用スコアに基づいて、前記経路を評価する、
プログラムを記憶する非一時的コンピュータ可読記憶媒体。
（付記１４）
前記経路集合の前記決定は、メタヒューリスティックアルゴリズムが実装する前記経路計画アルゴリズムを実行することによって低レベル探索が実行されるコンフリクトベース探索アルゴリズムの修正版を実行することを含む、
付記１３に記載の記憶媒体。
（付記１５）
前記経路計画アルゴリズムは、効用関数を使用して前記対象経路の前記効用スコアを計算し、
前記効用関数は、複数の目的項の重み付き和として定義され、各前記目的項は、その目的項に対応する前記目的が前記経路によって最適化される度合いを表す、
付記１３又は付記１４に記載の記憶媒体。
（付記１６）
前記複数の目的は、前記経路の効率性、前記経路の安全性、前記経路の平滑性、又はそれらの２つ以上を含む、
付記１５に記載の記憶媒体。
（付記１７）
前記経路計画アルゴリズムは、効用関数を使用して前記対象経路の前記効用スコアを計算し、
前記経路集合の前記決定は、
選択可能な手段で前記経路集合の複数の候補をユーザに提供することと、
前記ユーザが選択した前記経路集合の前記候補を示す情報を取得することと、
前記経路集合の前記選択された候補に基づいて新たな効用関数を生成することと、
前記新たな効用関数を使用して前記経路集合の新たな候補を決定することと、
前記ユーザに提供すべき前記経路集合の前記複数の候補のうちの１つを、前記経路集合の前記新たな候補に置き換えることと、
を、終了条件が満たされるまで繰り返し実行することを含む、付記１３から付記１６のいずれか一項に記載の記憶媒体。
（付記１８）
前記新たな効用関数の前記生成は、
前記ユーザが最後に選択した前記経路集合の前記候補を生成するのに使用される前記効用関数の構成を入力として使用するガウス過程によるベイズ最適化を実行し、それによって前記効用関数の新たな構成を取得することと、
前記取得した新たな構成を用いて前記新たな効用関数を生成することと、
をさらに含む、付記１７に記載の記憶媒体。

本出願は、２０２１年１２月８日に出願された日本特許出願第２０２１－１９８９８７号を基礎とする優先権の利益を主張し、その開示は参照によりその全体が本明細書に組み込まれる。

１０ 車両集合
２０ 車両
３０ エンティティ
４０ 経路集合
５０ 経路
６０ 車両情報
７０ 地図情報
８０ 候補経路
９０ 位置
１００ ウェイポイント
１１０ ウィンドウ
１２０ 入力インタフェース
１０００ コンピュータ
１０２０ バス
１０４０ プロセッサ
１０６０ メモリ
１０８０ ストレージデバイス
１１００ 入出力インタフェース
１１２０ ネットワークインタフェース
２０００ 経路探索装置
２０２０ 取得部
２０４０ MOMAPF 求解部
２０６０ 候補提供部
２０８０ 嗜好誘出部

Claims (10)

1. 車両情報及び地図情報を取得し、
   前記車両情報は複数の車両の各々について開始位置と目標位置の組を示し、前記地図情報は前記車両が移動する空間の地図を示し、
   前記車両情報と前記地図情報とを使用して、前記車両の各々について経路を含む経路集合を決定し、
   前記経路集合の前記経路は互いに競合せず、
   前記経路集合の前記決定は、経路計画アルゴリズムを実行して前記車両の各々について前記経路を生成することを含み、
   前記経路計画アルゴリズムは、複数の目的が前記経路によって最適化される度合いを表すスカラー値である前記経路の効用スコアに基づいて、前記経路を評価し、
   ２つの前記経路の競合は、少なくとも１つの時刻においてこれら２つの前記経路上の位置が互いに一致することを表す、経路探索装置。
2. 前記経路集合の前記決定は、メタヒューリスティックアルゴリズムによって実装される前記経路計画アルゴリズムを実行することによって低レベル探索が実行される、コンフリクトベース探索アルゴリズムの修正版を実行することを含む、
   請求項１に記載の経路探索装置。
3. 前記経路計画アルゴリズムは、効用関数を使用して前記経路の前記効用スコアを計算し、
   前記効用関数は、複数の目的項の重み付き和として定義され、
   各前記目的項は、その目的項に対応する前記目的が前記経路によって最適化される度合いを表す、
   請求項１又は請求項２に記載の経路探索装置。
4. 前記複数の目的は、前記経路の効率性、前記経路の安全性、前記経路の平滑性、又はそれらの２つ以上を含む、
   請求項３に記載の経路探索装置。
5. 前記経路計画アルゴリズムは、効用関数を使用して前記経路の前記効用スコアを計算し、
   前記経路集合の前記決定は、
   選択可能な手段で前記経路集合の複数の候補をユーザに提供することと、
   前記ユーザが選択した前記経路集合の前記候補を示す情報を取得することと、
   前記経路集合の前記選択された候補に基づいて新たな効用関数を生成することと、
   前記新たな効用関数を使用して前記経路集合の新たな候補を決定することと、
   前記ユーザに提供すべき前記経路集合の前記複数の候補のうちの１つを、前記経路集合の前記新たな候補に置き換えることと、
   を、終了条件が満たされるまで繰り返し実行することを含む、請求項１から請求項４のいずれか一項に記載の経路探索装置。
6. 前記新たな効用関数の前記生成は、
   前記ユーザが最後に選択した前記経路集合の前記候補を生成するのに使用された前記効用関数の構成を入力として使用するガウス過程によるベイズ最適化を実行し、それによって前記効用関数の新たな構成を取得することと、
   前記取得された新たな構成を用いて前記新たな効用関数を生成することと、
   をさらに含む、請求項５に記載の経路探索装置。
7. 車両情報と地図情報を取得することを含み、
   前記車両情報は複数の車両の各々について開始位置と目標位置の組を示し、
   前記地図情報は前記車両が移動する空間の地図を示し、
   前記車両情報と前記地図情報を使用する前記車両の各々についての経路を含む経路集合を決定することを含み、
   前記経路集合の前記経路は互いに競合せず、
   前記経路集合の前記決定は、経路計画アルゴリズムを実行して、前記車両の各々について前記経路を生成することを含み、
   前記経路計画アルゴリズムは複数の目的が前記経路によって最適化される度合いを表すスカラー値である前記経路の効用スコアに基づいて、前記経路を評価し、
   ２つの前記経路の競合は、少なくとも１つの時刻においてこれら２つの前記経路上の位置が互いに一致することを表す、
   コンピュータにより実行される制御方法。
8. 前記経路集合の前記決定は、メタヒューリスティックアルゴリズムが実装する前記経路計画アルゴリズムを実行することによって、低レベル探索を実行するコンフリクトベース探索アルゴリズムの修正版を実行することを含む、
   請求項７に記載の制御方法。
9. 車両情報と地図情報を取得することをコンピュータに実行させ、
   前記車両情報は複数の車両の各々について開始位置と目標位置の組を示し、
   前記地図情報は前記車両が移動する空間の地図を示し、
   前記車両情報と前記地図情報を使用して、前記車両の各々について経路を含む経路集合を決定することを前記コンピュータに実行させ、
   前記経路集合の前記経路は互いに競合せず、
   前記経路集合の前記決定は、経路計画アルゴリズムを実行して前記車両の各々について前記経路を生成することを含み、
   前記経路計画アルゴリズムは、前記経路によって複数の目的が達成される度合いを表すスカラー値である前記経路の効用スコアに基づいて、前記経路を評価し、
   ２つの前記経路の競合は、少なくとも１つの時刻においてこれら２つの前記経路上の位置が互いに一致することを表す、
   プログラム。
10. 前記経路集合の前記決定は、メタヒューリスティックアルゴリズムが実装する前記経路計画アルゴリズムを実行することによって低レベル探索が実行されるコンフリクトベース探索アルゴリズムの修正版を実行することを含む、
    請求項９に記載のプログラム。