論文
DBSJ Letters Vol.4, No.1――――――――――――――――――――――――――――――――――――

利用者コンテキストアウェアな歩行者ナビゲーションシステムの提案と利用可能性
Proposing a Context-aware PedestrianNavigation System and its Possible
Applications

上田 真由美♠ 西出 亮♦ 日裏 博之✧
川端 将之♥ 上島 紳一♣
Mayumi UEDA Ryo NISHIDE
Hiroyuki HIURA Masayuki KAWABATA
Shinichi UESHIMA
近年，移動体情報端末による歩行者ナビゲーションシステ
ムが注目されている．既存のサービスはコンテンツの豊富さや見せ方を重視し，提供経路は一様のものが多い．実際の利用を考えた場合，状況に応じた経路の提供が求められる．そこで我々は状況や目的を考慮した移動経路を提供する次世代の歩行者ナビゲーションシステムを提案する．本手法は，現実空間をマッピングした論理空間を構築して、コンテキストを付与し，Dijkstra の最短経路アルゴリズムを利用することにより，利用者の状況や目的に適応させた柔軟な移動経路を提供している．本稿では，シミュレーションにより提案手法の有効性を示し，さらにユビキタス社会における歩行者ナビゲーションシステムの利用可能性について検討する．
Recently, the remarkable advance on mobile terminal
technologies has enabled to develop full-scaled
navigation systems for pedestrians.
The authors
propose a context-aware pedestrian navigation system,
which provides users with the preferable route,considering the conditions of each area and the objectivesof the users, as a next-generation system. Metadata areutilized to represent logical space built over real space,
applying a scoring scheme dependent on context to findpaths to pedestrians’ destination. The usability of thesystem is examined in various environments bynumerical simulations, and possibilities of the system inpractical settings in the open area, with temporarily
built-up sites, are discussed.

1. はじめに
近年，モバイル通信環境の整備が進み，高性能な携帯電話やPDAなどの移動体情報端末を利用した歩行者ナビゲーションシステム(Pedestrian Navigation System, 以下PNSと記す)が注目され，実用段階のPNSサービスも存在する．このような状況の中，より充実したPNSサービスの実現を目指して，見せ方や付加情報の提示による効果的なナビゲーションに関する研究が行われている[1,2,3]．
実際にPNSを利用する場面を考えた際，歩行者は車や電車での移動と異なり，周囲の状況の変化に敏感に反応すると考えられる．さらに，状況に応じて，必ずしも最短経路を移動するとは限らない．本稿では，利用者の状況や目的に応じた移動経路を提供する「状況適応型歩行者ナビゲーションシス
テム(状況適応型PNS)」を提案している．本手法は，実空間の特徴をマッピングしたメッシュ状の論理空間を構築し，論理空間を用いた移動経路の探索を行う．本手法では，実空間の特徴を論理空間上にメタデータとして付与しており，各メタデータの持つ得点と利用者コンテキストによる得点を計算することによって，利用者の要求に応じた移動経路の提供を可能にする[4]．ここでは，シミュレーションにより提案手法の有効性を検証するとともに，提案手法の今度の利用可能性について検討する．
以下，2章では論理空間の表現手法と利用者コンテキストを考慮した経路探索手法について述べ，3章でプロトタイプシステムを用いたシミュレーションにより提案手法の有効性について検証し，4章で提案手法の今後の利用可能性について検討する．最後にまとめと今後の課題について述べる．

2. 状況適応型 PNS
利用者の求める移動経路を提供するには，単に目的地までの最短経路ではなく，利用者や周囲の状況を考慮した移動経路の提供が必要である．本章では，状況適応型 PNS を実現するための，論理空間の表現手法および利用者コンテキストを考慮した経路探索手法について述べる．

2.1 グラフ表現を用いた論理空間の構成
通常，ナビゲーションシステムでは地図データを用いている．しかし，地図データを用いた場合，図1に示すような屋根や街灯，段差といった空間の持つ情報を用いることが困難である．そこで本研究では，歩行者が移動する実空間をメッシュ状に区切り，格子点に囲まれた部分矩形領域に対して実空間の持つ特徴を付与した論理空間を構築する．本論理空間を用いることにより，部分矩形領域をノード，領域間を接続♠

正会員 名古屋大学 情報連携基盤センター
ueda@itc.nagoya-u.ac.jp♦
学生会員 関西大学総合情報学研究科博士後期課程
fa4d003@edu.kansai-u.ac.jp✧
学生会員 日立ソフトウェアエンジニアリング株式会社
h-hiura@hitachisoft.jp♥
学生会員 株式会社総合システムサービス
Masayuki.Kawabata@sgs.co.jp♣正会員 関西大学総合情報学部
ueshima@res.kutc,kansai-u.ac.jp

1

図 1 階層構造の論理空間と構成要素
Fig.1 Two-layered Logical Space and Its Constructs

日本データベース学会 Letters Vol.4, No.1

論文
DBSJ Letters Vol.4, No.1――――――――――――――――――――――――――――――――――――

図 2 空間属性を示すメタデータの例
Fig.2 Part of XML Schema of Metadata
するエッジとするグラフで表現でき，グラフ表記を用いた近似モデルによる経路探索問題として扱うことが可能となる．
本モデルでは，エッジの長さは一定値とし，歩行者の移動単位とする．このグラフに対してDijkstraの最短経路アルゴリズム適用することにより，経路集合を求めることができる．
ここで，出発地点をS(si,sj)，目的地をG(gi,gj)とすると，最短経路の長さLはマンハッタン距離 L = gi - si + gj - sj により算出することが可能である．本モデルでは，エッジの長さを一定値としているため，Dijkstraの最短経路アルゴリズムを適用した際，SからGへの最短経路は複数導出される．そこで本研究では，2.3節で述べる得点付け手法を用いてSからGへの最短経路を一意に決定し利用者に提供することを目指す．

2.2 空間特徴を表現するコンテキストの格納
利用者にとって理想的な歩行者ナビゲーションは，最短経路の提供ではなく，利用者個人の目的や状況，周囲の状況などを考慮した経路の提供である．実現には，実空間の持つ情報をシステムが把握することが必要となる．
実空間の持つ情報(空間属性)には，ビルや壁，階段といった移動を制限する移動制限物情報(図1下灰色部分)と，街灯や屋根，看板や広告といった状況に応じて必要となる状況依存物情報(図1下黄色部分)などが存在する．本研究では，これらの情報を各部分矩形領域に対して与えた，2層構造の論理空間を構成する(図1上)．すなわち，アーケードやビルは空間属性の1つとして屋根属性を持つ．このように定義する
ことにより，屋根属性を持つ領域を優先して，雨を避けた経路を提供することが可能になる．
本研究では，論理空間の記述精度とデータ量がトレードオフの関係になる．したがって，部分矩形は歩行者の移動を考え，約1mを一辺の長さとする．
各部分矩形領域は“location”タグの“ID”属性によって管理される(図2)．“ID”属性はその領域の中心点の緯度・経度情報とし，東経192度5分・北緯34度6分の地点の場合，<location id=”192.5, 34.6”></location>と表現する．さらに，この空間が持つ属性は“location”タグの子要素として記述する．
移動制限物情報は，“top_wall”，“bottom_wall”，“right_wall”，“left_wall”タグで記述し，状況依存物情報は“ceiling”，“light”，“crowd”，“steep”タグで記述する．ここでは，上述したように1m間隔のメッシュを形成しているため，ビルのように複数の部分矩形によって構成するオブジェクトが存在する．こ2Fig.3

図 3 コスト伝播モデルの例
Scoring Scheme for Partitioned Regionsのようなオブジェクトは，“building”タグを用いて記述し，該当メッシュの“location”タグの親要素となる．“building”タグは“ID”属性と“path”属性を持ち，通り抜け可能なオブジ
ェクトの場合，“pass”属性は“yes”の値をとる．

2.3 状況適応型経路探索のための得点付け手法
2.1節で述べたように，本システムではメッシュ間の長さを一定としているため，リンクの長さをコスト計算に用いる
Dijkstraのアルゴリズムを適応させて最短経路を一意に決定することは困難である．そこで，本節ではマンハッタン距離を用いた歩行者のための最適な移動経路探索を実現するエッジの得点付け手法について検討する．
出発地点Sを始点メッシュと呼び，目的地点Gを終点メッシュと呼ぶ．S，Gを結ぶ2.1節のマンハッタン距離Lを利用し，最短経路に近いメッシュ間のコストを低く，遠ざかるメッシ
ュ間のコストは遠ざかる距離に応じて高くなるように，全メッシュ間に得点付けを行う．その後，S，Gを基準とした正方形の波が広がるように各ノードにコストを与える．
以下，得点付けの手順を示す．
1.
出発地点SのコストはCs=0とする．
2.
Sを基準としたコストの波が広がるように各メッシュに得点付けを行う(図3 Step 1)．

Cs(N) = max( ni - Si , nj - Sj )3.
4.

（ただし，Cs(N)はノードNのSを基準とした得点付けによるコストをあらわす）
目的地点GのコストはCg=0とする．
手順2と同様によりGを基準とした得点付けを行う(図3Step 2)．

Cg(N) = max( ni - Gi , nj - Gj )5.

(2)

手順1〜4で算出された得点を合計したものを各メッシ
ュの得点とする．

C(N) = Cs(N) + Cg(N)
6.

(1)

(3)

メッシュ間のつながりをリンク長のコストとして扱うため，メッシュ間の平均得点を算出する(図3 Step 3, 4)．

E(N1, N2) = (C(N1) + C(N2))/2(4)

上記の手順を用いて得点付けを行うことにより，最小コストとなる経路がS，Gを結ぶ直線L付近となり，Lから離れるにつれてコストが増加する(図3 Step 3, 4)．

日本データベース学会 Letters Vol.4, No.1

論文
DBSJ Letters Vol.4, No.1――――――――――――――――――――――――――――――――――――

図 4 混雑を回避した場合の移動経路
Fig.4 Path Search Avoiding the Crowds
このコストの計算は，「三角形の二辺の和は，他の一辺より長い」という，三角形の公理に沿ったコストの算出法であり，最短経路Lからどの程度離れているかを示す指標となる．
式(4)により，ノード間の平均コストを計算し，各エッジに与えるため，Dijkstraのアルゴリズムを用いて最短経路を導くことが可能となる．図3右に上記の得点付け手法により算出した例を示す．SからGを結ぶルートAはC(S,G)=110，ルートBはC(S,G)=150となり，最短経路はルートAとなる．

2.4 状況適応型経路探索
2.3 節で述べた経路探索は，歩行者の目的や状況を考慮せずに，最短となる経路を提供する．そこで本節では歩行者の目的や状況に応じた経路を提供する手法について述べる．
状況に応じた経路提供は，2.3 節の手法による各ノードのコスト C(N)に，図 1 に示した空間属性コスト D(N)を加えることにより実現する(式(5))．

C(N) = pC(N) + (1 - p)D(N)for 0<p<1 (5)

ここでは，屋根や街頭，人ごみに対し 30 点，階段に 15 点と，図 1 に示した空間属性いった得点を定義している．式(5)において p はパラメータで，状況に応じて必要な空間属性が存在するメッシュに対して一様に正のコスト・負のコストを与える．これは，Dijkstra のアルゴリズムでは，総コストが最も低い(または最も高い)経路を解とするという特徴を持つためである．

3. プロトタイプシステム
本章では，プロトタイプシステムを用いて，利用シナリオに基づいたシミュレーションを行い，前章で述べた得点付け手法の有効性を検証する．
2 章で述べた得点付け手法を用いて利用者の目的や状況に応じて移動経路を提供する「状況適応型 PNS」のプロトタイプシステムを構築した．本プロトタイプシステムは，Java 2SDK(JDK1.5.0-beta2)を用いて構築し，論理空間は XML Ver1.0で記述し，XML パーサには DOM Level 1 を用いた．以下にシナリオに基づいたシミュレーションにより提案手法の有効性を示す．
シナリオ 1：屋外型イベント会場でベビーカーを押した子供連れの歩行者が，会場内の混雑した場所を避けて目的地であるブースに移動したい．
図 4 にシミュレーション結果を示す．図 4 では太線は壁が3

図 5 複数のコンテキストを考慮した経路探索例
Fig.5 Path Search Under Multiple Conditions
あることを示しており，壁に囲まれた部分は展示ブースや催物ブースなどがあることを示す．本シミュレーションでは，空間属性を考慮することにより変化する各メッシュのコスト確認が目的であるため，複合的な条件での経路探索ではな
く，混雑度属性のみを考慮した経路探索を行った．出発地点を(1.10)，目的地点を(19.4)と設定する．イベント会場では，混雑箇所(図 4○部分)の発生が考えられ，本シナリオのような子供連れの家族には，混雑を回避するルートの提供が求められる．このような場合，条件設定時に「混雑回避」と設定しておくことで，混雑箇所を回避した移動経路が提供される．
図 4 左は右の○部分付近を拡大したものと，該当箇所のコストを示している．このコストは式(5)により算出されたものである．

シナリオ 2：最寄りの駅から，夜間に会社のエレベータホールまで行きたい．さらに，雨と混雑を避け，安全で明るい道を通りたい．
図 5 にシミュレーション結果を示す．本シナリオでは，シナリオ 1 の混雑度属性に加えて，段差に対する情報，明るさ，屋根の有無，周辺の治安情報といった新しい条件を考慮する必要がある．本シミュレーションでは，本システムが領域毎にメタデータを指定でき，複雑な空間定義が可能であることを示している．すなわち，論理空間の個数や形状を問わないことを示している．
図 5 左は，出発地点を(1.1)，目的地点を(15.19)と設定し，利用者の要求を考慮せず，最寄りの駅から会社のエレベータホールまでの最短経路を示している．また，図 5 右には，条件を「雨」，「夜間」，「混雑回避」，「段差回避」，「治安良」と設定した場合の移動経路を示している．ここでは，見易さを考慮して矢印を表示している．雨を避けるため，屋根のある経路をとり，混雑を回避した経路を提供している．
図 5 下は A，B 部分を拡大し，コストを表示している．
「雨を避ける」設定のため，図 5 右の B で屋根のあるメッシュのコストが減少し，屋根がないメッシュのコストが上昇していることがわかる．B 付近のコストを計算しただけでは，通常時の経路(図 5 左 A 付近)の経路が総コストでは低くなるが，日本データベース学会 Letters Vol.4, No.1

論文
DBSJ Letters Vol.4, No.1――――――――――――――――――――――――――――――――――――
5. まとめ

図 6 簡易センサーを用いた実空間での利用例
Fig.6 Temporarily Built-up Sensor Network
Application in an Open Area
ビルは屋根属性がありコストが一様に減少している．それに対し，中央の道は一様にコストが上昇しているため，図 5 右のようにビルの内部を通る経路を提供している．さらに，「段差回避」を選択しているため，段差のあるメッシュのコストは上昇し，図 5 右(ビル内部)のように段差を避けた経路が提供される．

4. 提案手法の利用可能性
提案手法は，ユビキタス環境下で実用が可能であると考える．本システムは，出発地点と目的地点の入力による一様の移動経路提供ではなく，気温や湿度などの物理的条件や，屋根や路面状況，街頭設置状況，人の混雑度などを状況データとして捉え，論理空間に反映させることにより，利用者の目的や周囲の状況を考慮した移動経路を提供することが可能となる．
本システムは，論理空間内の各メッシュに対して状況を埋め込むことによって実現する．ここでは，今後の実空間での利用を可能にするため，動的に状況属性を収集する手法について検討する．実空間をセンサーによって矩形領域に分割し，状況属性を収集・配信する(図 6)．図 6 では，目的地点への最短経路上に混雑地点が存在することを示している．混雑地
点内いる利用者の携帯端末から混雑情報が送られるため，混雑を回避した移動経路を提供することが可能となる．このモデルは，室内型イベント会場のような場所で比較的容易に実現可能である．
適切にデータ取得を行うように，センサーやデバイスの設置を行うことにより，遊園地や博覧会のような屋外型イベント会場やビジネスショウなどの室内型イベント会場に適用することが可能となる．これらの会場で，入場券として携帯端末を貸与し，会場内に無線 LAN の基地を設置することによって，全ての利用者の動きを把握することが可能となり，入場者の少ない展示物への誘導や，混雑を避けて目的の会場やブースへ誘導することが可能である．また，無線 LAN に接続した携帯端末を持つことにより，主催者からの PUSH 型情報の提供を受けることも可能となる．多人数の利用には，サービスの軽量化が必要であるが，イベント会場など限られた空間での利用は容易に実現可能であると考える．さらに，イベント会場では，あらかじめデータ収集・提供の基準点として，簡易ポールなどを配置しメッシュの有線ネットワークを張り巡らすことで，データ取得の信頼性を高め，メッシュの構成を行うことは有効な手法であると考えられる(図 6)．

4

本稿では，実空間の特徴を論理空間に埋め込むことによって実現する状況適応型 PNS について述べた．本システムは，出発地点と目的地点により一様の移動経路を提供するのではなく，各利用者の目的や周囲の状況に応じて，利用者毎に異なる移動経路を提供することが可能である．
今後の課題として，膨大になるメッシュ間のつながりを考慮したデータ構造の仕組みの検討，実環境でのセンサーを用いたシミュレーション実験による提案手法の評価，利用者別の得点付け設定方法の導入による更なる個別化などの検討があげられる．

[謝辞]
本研究の一部は文部科学省私立大学学術研究高度化推進事業オープン・リサーチ・センター整備事業(平成 15 年度−20 年度)ならびに同サイバーキャンパス整備事業(平成 14 年度−16 年度)の一環として，また，同省「知的資産の電子的な保存・活用を支援するソフトウェア基盤技術の構築」プロ
ジェクトの支援により行われた．ここに記して感謝する．

[文献］[1] 藤井憲作，杉山和弘: “携帯端末向け案内地図作成システ
ム の 開 発 ”, 情 報 処 理 学 会 論 文 誌 , Vol.41, No.9,pp.2394-3003 (2000).
[2] 藤井憲作，杉山和弘: “歩行者ナビゲーション支援のための場所案内文作成手法”, 電子情報通信学会論文誌,D-Ⅱ
Vol.J82-DⅡ, No.11,pp.2026-2034, (1999).
[3] K.Lynch: “The Image of the City”, MIT Press (1960).
[4] 川端将之ら: “利用者コンテキストを考慮した歩行者ナビ
ゲーション方式の提案と利用可能性の検討”, 電子情報通信学会データ工学ワークショップ DEWS2005 3A-i12
http://www.ieice.org/iss/de/DEWS/DEWS2005/.

上田真由美

Mayumi UEDA

名古屋大学情報連携基盤センター研究員．2003 関西大学大学院総合情報学研究科博士後期課程修了，博士（情報学）．
データベースシステムおよび次世代コース管理システムの研究・開発に従事．情報処理学会，日本データベース学会，
ACM 正会員．

西出亮

Ryo NISHIDE

関西大学大学院総合情報学研究科博士課程後期課程在学中．
2004 関西大学総合情報学研究科博士課程前期課程修了．マ
ルチメディア情報システム，e-ラーニングシステムの研究・開発に従事．情報処理学会，ACM 学生会員．

日裏 博之

Hiroyuki HIURA

日立ソフトウェアエンジニアリング株式会社．2004 関西大学大学院総合情報学研究科博士課程前期課程修了．マルチメ
ディア情報システムの研究・開発に従事．情報処理学会会員．

川端 将之

Masayuki KAWABATA株式会社総合システムサービス．2005 関西大学総合情報学部卒業．マルチメディア情報システムの研究・開発に従事．

上島紳一

Shinichi UESHIMA

関西大学総合情報学部教授．1983 京都大学大学院工学研究科博士課程単位取得退学，工学博士．マルチメディア情報システムの研究・開発に従事．情報処理学会，ACM，IEEE CS等の会員．

日本データベース学会 Letters Vol.4, No.1