DEIM Forum 2014 P2-4

ナビ利用を伴う群集移動の分析に基づいた経路選択における集合知獲得手法の提案
浅川拓†

濱田恵輔†

中島 伸介†

北山 大輔††

角谷和俊†††† 京都産業大学 コンピュータ理工学部 〒 603–8555 京都府京都市北区上賀茂本山†† 工学院大学 情報学部 〒 163–8677 東京都新宿区西新宿 1 丁目 24–2††† 兵庫県立大学 環境人間学部 〒 670–0092 兵庫県姫路市新在家本町 1 丁目 1–12
E-mail: †{g1144029,g1044903,nakajima}@cse.kyoto-su.ac.jp, ††kitayama@cc.kogakuin.ac.jp,†††sumiya@shse.u-hyogo.ac.jp
あらまし事故, 渋滞, 災害等の突発的な理由により, 一部交通機関がマヒすることで目的地までの移動手段の選択に迷うことがある. その時の状況に応じて, ベストの選択を行うことは容易ではないが, 実際のナビ利用履歴を分析すれば, 比較的良好な経路を選択できたケースやそうでないケースを検出することが可能となる. 本研究では, ユーザの最終目的地までの過程において, ナビシステムにて推薦されたが選択しなかった経路と, 実際に選択した経路の特徴的な差異から, ユーザの経路決定に対する意図を抽出する技術を提案する. 特に経路選択としての成功例に着目することで,経路選択における集合知獲得が可能になると考えている.
キーワード

ナビゲーション利用履歴, 差異増幅アルゴリズム, 集合知

1. は じ め にユーザの経路選択データを分析することで, 比較的良好な経路を選択できたケースや, 反対に身動きが取れなくなるような経近年, 経路探索サービスの発展はめざましいものがある. 自路を選択してしまったケースを検出することが可能となる. そ動車に搭載されるカーナビゲーションシステム（以後, カーナこで, 比較的良好な経路を選択できたケースに着目し, これを分ビと略して記述する）は年間 5800 万台を超える出荷 [1] が行析することで経路選択に関する知識の獲得が可能ではないかとわれるほど広く普及しており, 目的地を設定すれば,VICS によ考えた. このような状況下で良好な選択をできたケースに基づる渋滞情報や高速道路の使用の有無等の条件を加味して, ユー

き, その経路が選択された理由を抽出して, これを集合知とする

ザにとって最適な経路を探索することができる. さらに, タブことで, 新規ユーザへの経路推薦に利用することを考える.

レット端末やスマートフォンの発展に伴い, 電車の乗り換え案

以上をふまえ, ナビを利用するユーザから経路選択のノウハ

内や歩行ルート案内等のサービスの利用も高まっている. 例え

ウを収集し, 他のユーザへの経路推薦に利用可能なデータ（集ば,NAVITIME（注 1）では, 有料サービスではあるが電車やバス,合知）を作成することを本研究の目的とする. 高品質, 高信頼な自動車, 飛行機, 徒歩等の移動手段を組み合わせたユーザにとっ知識（集合知）は, 実質的な社会活動の場であるリアル空間にて最適な経路を推薦するトータルナビゲーションサービスをこそ数多く存在すると考え, 実際の人々の経路選択の結果から行っている.

集合知の作成を目指す.

カーナビに関する研究としては, 特に経路探索手法について実際のユーザの経路選択データを分析する際, ナビシステム数多く行われており [2], ダイクストラ法 [3] や A *アルゴリズ

にて推薦されたが選択しなかった経路と, 実際に選択した経路

ム [4] といった最短経路探索のみならず, わかりやすく説明が容の特徴的な差異からユーザの経路決定に対する意向が含まれる易な経路を探索するアルゴリズム [5] のような, 様々なアルゴリと考え, その差異を増幅することで, ユーザの経路選択に関すズムを用いた手法が提案されている. また, ユーザの嗜好を反るノウハウの抽出に取り組む. この時の経路選択意図の推定手映した経路推薦に関する研究も多く行われている.

法としては, 差異増幅アルゴリズム [6] を適用する. 差異増幅ア

しかしながら, 突発的な事故や渋滞, 災害等により交通機関がルゴリズムとは, ユーザが”選択したもの”と”選択しなかったも一部マヒし, 推薦された経路でユーザが目的地に到着できないの”の特徴的な差異を比較し, これを増幅することで, 本来ユー場合がある（図 1 参照）. この場合, ユーザは, 代替の経路の選ザが求めていたものを推定する手法である.

択肢が増えるほど, 経路の選択に迷うことがある. 結果, ユーザは自身の経路選択基準（例えば,「費用が安い」等）に基づき

2. 関 連 研 究

経路を選択するが, その状況下におけるベストな経路を選択す

歩行者の嗜好に合わせた経路を提示するために, 松田ら [7] はることは容易ではない. そのような様々な状況において実際の100〜200 人規模のアンケート調査を 2 回行い, 結果の分析を（注 1）：http://www.navitime.co.jp

好を表現することが可能となっている. 具体的には, 歩行者は距行った. この研究は, アンケート調査を個人単位で行うことで嗜図 1 提案手法の概要

離以外に経路上の階段の有無などの快適性や, ガードレールや向かっていたものとする. ここで, ナビの示す中央の経路が事横断歩道有無などの安全性を重視し, 年齢や性別に応じて重視

故・災害等により通行不能になったケースを想定する. この時,する条件が異なるという知見を得ている. しかし, これらの条ユーザが代替経路として選択出来るのはバスに乗るルートと電件内の各要因はアンケート内容に制限されるが, 差異増幅アル車に乗るルートがあり, ユーザ自身の判断により最も早く目的ゴリズムでは制限される要因はなく, 様々な条件下での経路選地へ到着できるであろう経路を選択する.

択履歴からユーザの意向を反映できるものである. また, 災害

この時の経路選択における正解（最短で到着できる経路）は,や事故等の突発的な事象により, 推薦された経路が歩行できな平常時の予想到達経路を比較しても意味がない. 例えば, 元の推いといった場合には適用が難しい.

薦経路が不通になった原因が他の経路にも影響がでるケースや,狩野ら [8] は, 動的にコストを変動させるアルゴリズムを用い直接的には影響がなくても他の経路からユーザが流入してくるて, 数分毎に道路のコストデータを更新し, 渋滞回避を可能にすことによる渋滞などにより間接的な影響がでるケースが考えらる手法の研究を行っている. しかし, このシミュレータでは渋れる. この時のユーザの判断基準を収集・分析するためには, こ滞や事故, 工事等の情報のみ考慮しているため, 運転者が経路をのような状況を表現することが可能なコンテキストデータの収変更した場合, その理由は渋滞や事故, 工事等に限られる. また,集が必要である.

明示された交通情報のみ適応可能であるため, 突発的な渋滞や事故に対応出来ない.

そこで収集するデータ項目としては, 以下のような項目を検討している.

根笹ら [9] は, 運転者の提示する条件に合わせて経路推薦を・出発地情報（緯度・経度）行うアルゴリズムの研究を行っている. しかしながら運転者が・目的地情報（緯度・経度）提示する条件は, 立寄地や道路の種類・大きさなどに限られて・出発日時いる.

・不通状態発生日時
・不通原因種別（地震, 停電, 自然渋滞, 交通事故,・・・）

3. ナビ利用を伴う群集移動の分析に基づいた経路選択における集合知獲得手法

・不通状態発生後のその他選択可能経路

本節では, ナビ利用を伴う群集移動の分析に基づいた経路選・ユーザが選択した経路・その他選択経路への影響の有無

択における集合知獲得手法について説明を行う. 経路選択デー

・目的地到達日時

タからユーザの意向を抽出するには, 大きく分けて２つの方法

上記のようなデータを収集することで, ユーザの判断基準のが必要となる. １つ目はユーザの経路選択データの収集方法, ２分析が可能になると考えている.

つ目はユーザの経路選択データを分析し, 経路選択の意向を抽

実際のデータ収集方法としては, 自動車移動の場合はカーナ出する方法, である. そこで,3. 1 節で”ユーザの経路選択データ

ビゲーションの利用履歴, その他ユーザ移動の場合は歩行者ナの収集方法”,3. 2 節で”ユーザの経路選択に基づく集合知獲得方ビの利用履歴の利用を想定している. しかしながら, これらデー法”について説明を行う.

タは公開されていないため, 最終的にはナビゲーションサービ

3. 1 ユーザの経路選択データの収集方法

スを行っている企業との連携を模索しなければならないと考え

本節では, ユーザの経路選択の結果を収集する方法を説明すている. したがって, まずは提案手法の有効性を示す必要がある

る. 以下, 図 1 に示した状況で手法を説明する.
ユーザはナビに従って出発地から中央の経路を通って目的にため, 当面はユーザアンケート等に基づいた人工的なナビ利用履歴データを作成し, 提案手法の有効性および妥当性の評価を行いたいと考えている.

3. 2 ユーザの経路選択に基づく集合知獲得方法
3. 2. 1 経路選択意図分析方法の概要
同一もしくは同様の状況（コンテキスト）にて, 経路選択を行ったユーザ群から収集した経路選択データを対象に, 差異増幅アルゴリズム等を用いることで, 各ユーザの経路選択意図を分析し, これを統計的に分析することで, 経路選択に関する集合
図 2 収集した経路選択データの分析

知の獲得を目指す.
事故・災害等の非常時において, このような選択をすれば常に最適ルートを選択できるという普遍的な解は存在せず, そ路選択時の判断基準を分析する（図 2 参照）.の時その時のシチュエーションによって, 最適ルートは変化す抽出された経路探索時の判断基準のうち, 結果的に良好な判るものである. したがって, ある時偶然に最適な経路選択ができ断（比較的短時間で目的に到着）であり, 同一条件（もしくはたとしてもそのユーザの判断基準が常に優れている訳ではない.

同様の条件）にて多数のユーザに支持された場合には, この状

つまり, その時その時の非常時において群集はどのような判断

況（コンテキスト）における適切な判断（経路探索における集をし, 最終的にどのような経路選択を行っているのか, 群集の経合知）として採用する. この時の状況（コンテキスト）の表現

路選択パターンの中でどのような経路選択方法が比較的に良好

においては, 固有の地名（例えば, 京都駅や新宿駅など）としてな経路選択が行えているのか, ということを分析することで, 経表現するだけでなく, その地域における役割など等を表す抽象路選択に関する集合知の獲得が可能になると考えている. この度を上げた表現（新幹線の乗り入れがある JR の駅,JR や私鉄様にして, 経路選択に関する集合知を獲得できれば, 経験値の少等の乗り換え駅, バスターミナル隣接など）として, 状況（コンないユーザに対しても, 多くの人々に受け入れやすい比較的良テキスト）を表現することを試みる. これにより, 同一地域のみ好な経路選択を推薦できると信じている.の集合知としてではなく, 他の地域やその他の状況への適用も

3. 2. 2 差異増幅に基づく経路選択に関する集合知の獲得
ユーザの経路選択の理由を分析する方法として, 差異増幅アルゴリズムを用いるが, 差異増幅アルゴリズムとは, ユーザが選択したものと可能になると考えている.

3. 2. 3 経路選択に関する集合知に基づく経路推薦方式
経路選択に関する集合知に基づく最も手堅い経路推薦方法としては, 同一エリアにおける同様の事故・災害等が発生した場合選択しなかったものの特徴的な差異を比較し, これを増幅することで, 本来ユーザがにおいて, 適切な経路を選択できないユーザに対して, これまで求めていたものを推定しようとする手法である.に得られた集合知に基づいて経路を推薦する方法である. 前節

ユーザの嗜好の表れである 選択したもの のみを分析するでも説明したが, 経路選択における集合知について, その時の状選択したもの

は総合的には況を抽象度を上げて表現し, これを特徴ベクトル化することがポジティブに判断されたということがいえるが,選択したもできれば, 同一エリアや同一の事故・災害等のトラブルに限らが有する全ての要素がポジティブということではない. たずに, 類似した状況における過去の集合知の利用が可能になる.

方法との違いについて述べる.のが有する要素のうち, 何がポジティブでただし, これを実現するためには, 出発地, 目的地の特徴の抽象何がポジティブでないかを 選択したもの のみで判断するこ化, 選択可能なルートの抽象化および特徴ベクトル化, 事故・災とは不可能である.

害等のトラブルの種別や影響の大きさに関する特徴ベクトル化

だし選択したものそこで, 選択したもの と 選択しなかったもの の差異になどについて検討する必要がある. 今後は, 経路選択を行う際の注目している. 選択したもの と 選択しなかったもの を比状況データ（コンテキスト）の抽象化や特徴ベクトル表現につ較すると, それぞれが持つ要素は,いて取り組むと共に, 評価実験が可能なプロトタイプシステム・ 選択したものの構築に取り組む予定である.

のみに現れる要素

・ 選択しなかったもの

のみに現れる要素

・両者に共通して現れる要素

4. 簡 易 実 験のそれぞれに分類することができる. つまり, 選択したも提案手法の意義を確認する為に簡単な実験を行った. 内容

のみに現れる要素には, そのユーザがポジティブな印象をは,20 代学生 10 名を対象にアンケートを取り通行中の経路が持った可能性があり, 選択しなかったもの のみに現れる要素不通となった際に選択する代替経路と, その理由を記入してもには, ネガティブな印象を持った可能性がある. これにより, 単らった. アンケート内容は以下の通りである.に『京都駅から京都産業大学に向かおうとしている所で, 地下鉄の選択したもののみに注目するよりも, より詳細にユーザ烏丸線の烏丸御池駅で事故が発生し, 四条以北が不通になりまの判断基準の分析を行えるようになる.
そこで, この差異増幅アルゴリズムを経路選択に適用し,した. このとき代替ルートとしてどのルートを通るか, 提示したユーザが代替経路として選択したルート５つの中から１つ選択してください. また, そのルートを選択しとユーザが代替経路として選択しなかったルートの特徴の差異に注目し, これを増幅処理することで, ユーザの経た理由を１つ選択してください.』
選択経路としては, 以下の５つのルート (図３参照) を提示し被図 3 選択経路の図

験者に選択した経路を記入してもらった.

À京都駅→烏丸四条→市バス上賀茂神社前→産大前 乗り換え 2回 430 円 63 分

Á京都駅→産大前 乗り換え 1 回 220 円 105 分
Â京都駅→京阪七条→京阪出町柳→産大前 乗り換え 1 回 徒歩15 分 580 円 63 分
Ã京都駅→京阪七条→京阪出町柳→叡山二軒茶屋→産大前 乗り
換え 2 回 徒歩 15 分 580 円 46 分

Ä京都駅→北大路→産大前 乗り換え 1 回 440 円 60 分アンケートの結果は経路Áが 6 人, 経路Äが 4 人となった. 経路Ãについては, 所要時間が 46 分と最も早く目的地に到達する経路であるにも関わらず, 選択されなかった. また経路Äは大きな特徴が見られないが 4 人に選択されている. この結果から単純な数値の比較だけでは判断できないノウハウが存在する事が分かる. 以上の事から “突発的な事故の発生により普段通っている経路が通行できない場合の代替経路”に関するユーザの選択にはある程度の偏りが確認できる. よって, ある地域について熟知しているユーザグループの中には何らかの集合知が存在し,このような集合知を適切に集約することで, 非常時における適切なナビゲーションの実現を目指す.

5. お わ り に本研究では, ナビ利用を伴う群集移動の分析に基づいた経路選択における集合知獲得手法の提案を行った. なお, 経路選択に関する集合知の獲得には, 差異増幅アルゴリズムの適用を検討している. 本提案手法に基づいた経路推薦システムが開発できれば, 事故・災害等の非常時において, 過去の経験から得られた集合知に基づく経路推薦が可能になると考えている.
今後は, 経路選択を行う際の状況データ（コンテキスト）の抽象化や特徴ベクトル表現について取り組むと共に, 評価実験が可能なプロトタイプシステムの構築に取り組む予定である.

文献[1] 国土交通省道路局『カーナビ・VICS の出荷台数』2012 年 9 月

末時点[2] 独立行政法人 工業所有権情報・研修館『カーナビ経路探索技術』, 2005
[3] E. W. Dijkstra, “A note on two problems in connexion withgraphs,” Numerische Mathematik, vol. 1, no. 1, pp. 269–271, Dec. 1959.
[4] P. Hart, N. Nilsson, and B. Raphael, “A Formal Basis for theHeuristic Determination of Minimum Cost Paths,” IEEETransactions on Systems Science and Cybernetics, vol. 4,no. 2, pp. 100–107, 1968.
[5] Matt Duckham, Lars Kulik, Simplest Paths: AutomatedRoute Selection for Navigation, Spatial Information Theory. Foundations of Geographic Information Science, Lecture Notes in Computer Science Volume 2825, pp 169-185,
2003[6] 中島伸介, 木下真一, 田中克己. 差異増幅型適合フィードバックに基づく画像データベース検索. 電子情報通信学会論文誌（データ工学特集号）VOL.J87-D1 No.2,pp.164-174,2004.
[7] 松田 三恵子, 杉山 博史, 土井 美和子, 歩行者の経路への嗜好を反映した経路生成, 空間情報認知適正の基礎と応用論文特集,2004.
[8] 狩野均, 小塚英城,CA 法による広域道路交通シミュレータを用いた経路案内方式の評価, 情報処理学会,ITS 研究会,2002.
[9] 根笹 賢一, 宮岡 伸一郎, カーナビ経路探索における運転者希望
経路の反映, 情報処理学会研究報告.MBL 2007.