(57)【要約】【課題】カフェ等の動的障害物が存在し得る環境下において、スタート地点からゴール地点までの経路を探索して自走する。【解決手段】自走式画像形成装置１２は、カフェ１０等においてスタート地点Ｓからゴール地点Ｇまでの経路を探索する際に、自走可能領域内の動的障害物情報を用いる。過去に動的障害物情報が存在するルートの遭遇確率を高く設定し、各ルートのうち、最低の遭遇確率のルートを選択する。現に動的障害物が存在する場合、当該ルートの遭遇確率を１として選択しないようにする。【選択図】図１
2014209293.tif 000002
【特許請求の範囲】
【請求項１】
静的障害物を回避してスタート地点からゴール地点に到達できる経路を探索する手段と、
探索して得られた前記経路のそれぞれに対し、過去に蓄積された動的障害物情報を用いて動的障害物との遭遇確率を算出する手段と、
探索して得られた経路のうち、前記遭遇確率が最も小さい経路を選択する手段と、
を備えることを特徴とする経路探索装置。
【請求項２】
前記選択する手段は、探索して得られた経路のうち、前記遭遇度合が最も小さい経路が複数存在する場合に、前記スタート地点から前記ゴール地点までの距離が最も短い経路を選択する
ことを特徴とする請求項１に記載の経路探索装置。
【請求項３】
動的障害物を検出する手段と、
を備え、
前記算出する手段は、前記検出する手段で現に動的障害物を検出している経路の前記遭遇確率を１として算出する
ことを特徴とする請求項１に記載の経路探索装置。
【請求項４】
動的障害物を検出する手段と、
を備え、
前記算出する手段は、前記検出する手段で現に動的障害物を検出している経路の前記遭遇確率を、動的障害物までの距離が小さいほど大きくなるように算出する
ことを特徴とする請求項１に記載の経路探索装置。
【請求項５】
動的障害物を検出する手段と、
選択した経路に沿って移動している間に前記経路上に動的障害物を検出した場合に、それ以上前記経路に沿って移動すると後戻りが必要になるか否かを判定し、後戻りが必要と判定された場合にその地点から前記ゴール地点に到達できる経路を再探索する手段と、
を備えることを特徴とする請求項１記載の経路探索装置。
【請求項６】
前記スタート地点及び前記ゴール地点を含む移動可能領域を複数のグリッドに分割し、前記グリッド毎に前記動的障害物情報が割り当てられ、
前記算出する手段は、探索して得られた前記経路上に存在するグリッドに割り当てられた前記動的障害物情報を用いて前記遭遇確率を算出する
ことを特徴とする請求項１記載の経路探索装置。
【請求項７】
請求項１〜６のいずれかに記載の経路探索装置と、
選択した経路に沿って前記ゴール地点まで自走する走行制御装置と、
を備えることを特徴とする自走式作業装置。
【請求項８】
出発地点から目的地点までの経路を、静的障害物情報に基づいて決定する決定手段と、
前記決定手段により決定された経路のそれぞれに対し、過去の動的障害物の出現の記録である動的障害物情報を用いて動的障害物との遭遇確率を算出する算出手段と、
前記算出手段により算出された動的障害物との遭遇確率が最も小さい経路を選択する選択手段と、
を有する経路探索装置。
【請求項９】
コンピュータを、
静的障害物を回避してスタート地点からゴール地点に到達できる経路を探索する手段と、
探索して得られた前記経路のそれぞれに対し、過去に蓄積された動的障害物情報を用いて動的障害物との遭遇確率を算出する手段と、
探索して得られた経路のうち、前記遭遇確率が最も小さい経路を選択する手段
として機能させることを特徴とするプログラム。
【請求項１０】
コンピュータを、
静的障害物を回避してスタート地点からゴール地点に到達できる経路を探索する手段と、
探索して得られた前記経路のそれぞれに対し、過去に蓄積された動的障害物情報を用いて動的障害物との遭遇確率を算出する手段と、
探索して得られた経路のうち、前記遭遇確率が最も小さい経路を選択する手段
として機能させるプログラムを記録する、コンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路探索装置、自走式作業装置、プログラム及び記録媒体に関する。
【背景技術】
【０００２】
従来から、スタート地点からゴール地点までの最短ルートを探索／選択する技術が開発、提案されている。
【０００３】
下記の特許文献１には、マップ状に記憶された走行経路に従って作業を行う自動式作業車のためのマップ記憶方法において、自走式作業車が走行する領域に、領域の状態に応じた属性を持たせてマップに登録すること、及び当該マップを用いて作業車の走行作業経路を作成することが記載されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開平８−１６２４１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ところで、近年では、オフィスの生産性向上を図るため固定した机を持たずに自由に場所を選べるフリーアドレスを採用する企業が増加し、クラウドを利用したモバイルワークも普及しつつある。従って、カフェ等のオープンな場所において作業する場合もあり、プリンタ等に代表される画像形成装置を自走式とし、利用者の近傍まで自走させて所望のプリントジョブを実行することでセキュリティを担保することは重要である。この場合、自走式の画像形成装置には、スタート地点から利用者の存在するゴール地点までの経路を探索し、探索して得られた経路に従って自走する機能が求められる。
【０００６】
通常、スタート地点からゴール地点に到達可能な複数個の経路を探索し、これら複数個の経路の中から最短距離を最適経路として選択することになる。しかしながら、カフェ等の環境では人々が各種の目的をもって自発的に移動するため、人々が経路上に移動する場合も想定され、人々が自走式画像形成装置にとって動的障害物となり得る。
【０００７】
例えば、カフェの場合、レジや食器返却口の前、商品の受け取り台近傍は多くの人々が存在し得る場所であり、仮に、自走式画像形成装置が選択した経路上にこれらの場所が含まれている場合、人々と干渉するため選択した経路に沿って自走することができなくなる。経路上に人々等の動的障害物が存在する場合、
（１）動的障害物が存在しなくなるまで待機する
（２）経路を空けるように何らかのサインを送る
（３）経路を再探索（リルート）してゴールを目指す
が解決策として考えらえるが、
（１）では、障害物が直ぐに経路から外れる場合もある一方、長時間経路から外れない場合もあり得るので一定時間内に確実にゴールに到達できる保証がない
（２）では、たとえサインを送っても相手が気付かない場合もあり、かつ、誰にサインを送っているのかも不明である
（３）では、それまでに走行した経路を引き返す分だけ時間が無駄になる
等の問題があり、いずれも有効な対策とは言えない。
【０００８】
本発明の目的は、動的障害物が存在する領域において、速やかにゴールまで到達し得る経路を探索する経路探索装置及び自走式作業装置を提供することにある。
【課題を解決するための手段】
【０００９】
請求項１記載の発明は、静的障害物を回避してスタート地点からゴール地点に到達できる経路を探索する手段と、探索して得られた前記経路のそれぞれに対し、過去に蓄積された動的障害物情報を用いて動的障害物との遭遇確率を算出する手段と、探索して得られた経路のうち、前記遭遇確率が最も小さい経路を選択する手段とを備えることを特徴とする経路探索装置である。
【００１０】
請求項２記載の発明は、前記選択する手段は、探索して得られた経路のうち、前記遭遇度合が最も小さい経路が複数存在する場合に、前記スタート地点から前記ゴール地点までの距離が最も短い経路を選択することを特徴とする請求項１に記載の経路探索装置である。
【００１１】
請求項３記載の発明は、動的障害物を検出する手段とを備え、前記算出する手段は、前記検出する手段で現に動的障害物を検出している経路の前記遭遇確率を１として算出することを特徴とする請求項１に記載の経路探索装置である。
【００１２】
請求項４記載の発明は、動的障害物を検出する手段とを備え、前記算出する手段は、前記検出する手段で現に動的障害物を検出している経路の前記遭遇確率を、動的障害物までの距離が小さいほど大きくなるように算出することを特徴とする請求項１に記載の経路探索装置である。
【００１３】
請求項５記載の発明は、選択した経路に沿って移動している間に前記経路上に動的障害物を検出した場合に、それ以上前記経路に沿って移動すると後戻りが必要になるか否かを判定し、後戻りが必要と判定された場合にその地点から前記ゴール地点に到達できる経路を再探索する手段とを備えることを特徴とする請求項１記載の経路探索装置である。
【００１４】
請求項６記載の発明は、前記スタート地点及び前記ゴール地点を含む移動可能領域を複数のグリッドに分割し、前記グリッド毎に前記動的障害物情報が割り当てられ、前記算出する手段は、探索して得られた前記経路上に存在するグリッドに割り当てられた前記動的障害物情報を用いて前記遭遇確率を算出することを特徴とする請求項１記載の経路探索装置である。
【００１５】
請求項７記載の発明は、請求項１〜６のいずれかに記載の経路探索装置と、選択した経路に沿って前記ゴール地点まで自走する走行制御装置とを備えることを特徴とする自走式作業装置である。
【００１６】
請求項８記載の発明は、出発地点から目的地点までの経路を、静的障害物情報に基づいて決定する決定手段と、前記決定手段により決定された経路のそれぞれに対し、過去の動的障害物の出現の記録である動的障害物情報を用いて動的障害物との遭遇確率を算出する算出手段と、前記算出手段により算出された動的障害物との遭遇確率が最も小さい経路を選択する選択手段とを有する経路探索装置である。
【００１７】
請求項９記載の発明は、コンピュータを、静的障害物を回避してスタート地点からゴール地点に到達できる経路を探索する手段と、探索して得られた前記経路のそれぞれに対し、過去に蓄積された動的障害物情報を用いて動的障害物との遭遇確率を算出する手段と、探索して得られた経路のうち、前記遭遇確率が最も小さい経路を選択する手段として機能させることを特徴とするプログラムである。
【００１８】
請求項１０記載の発明は、コンピュータを、静的障害物を回避してスタート地点からゴール地点に到達できる経路を探索する手段と、探索して得られた前記経路のそれぞれに対し、過去に蓄積された動的障害物情報を用いて動的障害物との遭遇確率を算出する手段と、探索して得られた経路のうち、前記遭遇確率が最も小さい経路を選択する手段として機能させるプログラムを記録する、コンピュータ読み取り可能な記録媒体である。
【発明の効果】
【００１９】
請求項１，８，９，１０記載の発明によれば、動的障害物が出現しても、効率的にゴール地点に到達するための経路が得られる。
【００２０】
請求項２記載の発明によれば、遭遇確率が同一の場合でも最適と思われる経路が得られる。
【００２１】
請求項３、４記載の発明によれば、現に経路上に動的障害物が出現してもこれを踏まえた最適経路が得られる。
【００２２】
請求項５記載の発明によれば、現に経路上に動的障害物が出現しても、適当な位置若しくはタイミングで経路が再探索される。
【００２３】
請求項６記載の発明によれば、動的障害物情報を効率的かつ漏れなく活用した経路が得られる。
【００２４】
請求項７記載の発明によれば、得られた経路に沿ってゴール地点まで到達し、所定の作業を実行できる。
【図面の簡単な説明】
【００２５】
【図１】実施形態の経路探索説明図である。
【図２】実施形態の経路探索説明図である。
【図３】実施形態の自走可能領域説明図である。
【図４】実施形態の動的障害物マップ説明図である。
【図５】実施形態の経路探索説明図である。
【図６】実施形態のマップ重畳説明図である。
【図７】実施形態の動的障害物出現時の経路探索説明図である。
【図８】実施形態の構成ブロック図である。
【図９】実施形態の動的障害物情報説明図である。
【図１０】実施形態のマップ情報説明図である。
【図１１】実施形態の動的障害物蓄積情報説明図である。
【図１２】実施形態の処理フローチャートである。
【図１３】他の実施形態の処理フローチャートである。
【図１４】他の実施形態の経路再探索説明図である。
【図１５】他の実施形態の経路再探索説明図である。
【図１６】他の実施形態の経路再探索説明図である。
【図１７】さらに他の実施形態の報知説明図である。
【発明を実施するための形態】
【００２６】
以下、図面に基づき本発明の実施形態について、自走式作業装置として自走式画像形成装置を例にとり、かつ、カフェ内において経路を探索してゴールまで自走する場合を例にとり説明する。但し、本発明はこれに限定されるものではない。
【００２７】
＜本実施形態の基本原理＞
まず、本実施形態における経路探索の基本原理について説明する。
【００２８】
図１に、カフェ１０の平面図の一例を示す。カフェ１０内にはテーブルや椅子、レジ、食器返却口、商品の受け取り台等の各種施設、設備が存在する、カフェ１０内の人々は、代金を支払う、商品を受け取る、食器を返却する等の各種目的のために移動する。図において、実線１００は、カフェ１０内の人々の移動軌跡、すなわち動線を示す。実線１００の典型例は、カフェ１０の出入口から入り、レジにて支払いを済ませ、コーヒーを受け取り、椅子に着席し、食器を返却し、出入口から退出するというものである。
【００２９】
今、利用者がカフェ１０内に入り、ゴール地点（図中Ｇで示す）の椅子に座ってモバイル機器を操作して所定の作業を行い、スタート地点（図中Ｓで示す）で待機している自走式画像形成装置１２にプリントジョブを依頼したとする。この場合、自走式画像形成装置１２は、スタート地点からゴール地点までの経路を探索し、探索して得られた経路に沿ってゴール地点まで自走し、ゴール地点でプリントジョブを実行する。スタート地点からゴール地点の間には、静的障害物及び動的障害物が存在する。ここで、静的障害物とは、壁、柱、テーブル、観葉植物等、一定時間以上静止している障害物をいう。また、動的障害物とは、人、椅子、鞄、傘等、客自身か客の持ち物か、客が一時的に使用し、客の意思によって移動させることが可能な障害物をいう。
【００３０】
自走式画像形成装置１２は、静的障害物の位置を検出し、カフェ１０内で自走式画像形成装置１２が自走可能な領域のうち、静的障害物と干渉しない経路を探索する。経路探索方法としては、公知の方法を用いることができる。経路探索により、スタート地点からゴール地点に到達し得る２つの経路が探索されたとする。図において、これら２つの経路を経路２００ａ及び経路２００ｂで示す。
【００３１】
経路２００ａの方が経路２００ｂよりも経路長が短いため、最短距離の経路を選択するとのアルゴリズムに従えば、自走式画像形成装置１２は経路２００ａ，２００ｂのうち、経路２００ａを選択することになる。
【００３２】
しかしながら、経路２００ａは実線１００で示す動的障害物の動線と干渉しているため、図２に示すように、例えばカフェ１０の客が移動することによって経路２００ａ上に動的障害物として存在する場合が生じる。この場合、図２に示すように、自走式画像形成装置１２は、まずは経路２００ａに沿って自走を開始するが、人々等の動的障害物に遭遇し、このため来たルートをそのまま引き返してスタート地点に戻り、代替ルートとして経路２００ｂを選択して経路２００ｂに沿って自走することになり、結局、これらを含めた経路２５０に沿って自走することとなり、無駄な時間を要することになる。
【００３３】
そこで、本実施形態では、図１のようにゴールに到達し得る経路が複数存在する場合に、動的障害物の動線１００と干渉するような経路については優先順位を下げて、自走中に動的障害物と遭遇して障害回避処理が発生しないように制御する。図１の場合、経路１００ａは動的障害物の動線１００と干渉するため優先順位を下げる一方、経路２００ｂは最短距離ではないものの動的障害物の動線１００と干渉しないため、優先順位を下げることはしない。これにより、自走式画像形成装置１２は、最短経路でない経路２００ｂを最適経路に選択し、経路２００ｂに沿って自走を開始する。
【００３４】
図３に、自走式画像形成装置１２が保有するマップを示す。自走式画像形成装置１２は、カフェ１０内を示すマップとともに、静的障害物を除外した自走可能領域１４をマップとして記憶する。自走式画像形成装置１２の演算処理装置は、このマップに基づいてゴール地点に到達する経路を探索する。自走可能領域１４を示す座標は、固定的なものではなく、自走中の静的障害物検出をトリガとして自動的に補正（領域の追加及び削除）が可能である。
【００３５】
他方、自走式画像形成装置１２は、このようなマップとは別に、過去の障害物蓄積情報（座標、曜日、時間、障害物の種類）を記憶する。自走式画像形成装置１２は、過去の障害物情報を、自走式画像形成装置１２が備えるセンサ、又はカフェ１０の所定位置に設置したセンサ（カメラや超音波等）によって常時収集して記憶する。
【００３６】
図４に、収集した過去の障害物蓄積情報を有するマップ１６の一例を示す。マップ１６は、対象領域をグリッド化し、グリッド単位で過去の障害物情報を収集したものである。図において、過去に障害物が存在したグリッド１８にはハッチングが付されている。各グリッドの障害物情報は、既述したように、座標、曜日、時間、障害物の種類が含まれる。
【００３７】
図５に、自走可能領域１４のマップを用いてスタート地点Ｓからゴール地点Ｇまで経路探索して得られる、ゴール地点に到達可能な経路を示す。経路２００ａ及び経路２００ｂが到達可能な経路として演算される。この図に、図４に示す障害物情報５０を含むマップ１６を重ねた結果を示す。図６の経路２００ａ、２００ｂと、マップ１６とを照合すると、経路２００ａには過去に障害物が存在したグリッド１８が存在しており、経路２００ａに沿って自走した場合には障害物に遭遇し、何らかの障害物回避処理を実行しなければならない場合が生じ得ることがわかる。一方、経路２００ｂには過去に障害物が存在したグリッド１８が存在しておらず、経路２００ｂに沿って自走した場合には障害物に遭遇せず、障害物回避処理も実行する必要がない可能性が高いことがわかる。
【００３８】
そこで、自走式画像形成装置１２は、図６のマップから、経路２００ａの優先順位を低下させ、経路２００ｂをゴール地点Ｇに到達するための最適経路として選択する。
【００３９】
このように、本実施形態では、動的障害物と干渉する可能性のある経路は選択せず、たとえ最短距離でなくても動的障害物と干渉しない経路を選択する。ここで、動的障害物と干渉するか否かは過去の障害物情報に基づいて判定するため、過去の障害物情報には存在しない新たな動的障害物が選択した経路上に出現する場合も想定され得る。
【００４０】
図７に、この場合の状況を示す。自走可能領域１４においてスタート地点Ｓからゴール地点Ｇに到達可能な経路２００ａ、２００ｂのうち、経路２００ａについては過去の障害物情報５０が存在し動的障害物と干渉するため優先順位を低下させ、経路２００ｂを最適経路として選択したものの、ゴール地点Ｇに向かって自走する間、人等の動的障害物２０ｇが経路２００ｂ上に新たに出現し、これを自走式画像形成装置１２が備えるセンサ若しくはカフェ１０の所定位置に設けられたセンサで検出する場合がある。
【００４１】
この場合、経路２００ｂにも動的障害物２０が存在するため、動的障害物の観点からは経路２００ａと経路２００ｂは同一条件となるが、自走式画像形成装置１２は、経路２００ｂではなく経路２００ａを最適経路として選択する。その理由は、障害物情報５０は過去の障害物情報であって障害物と干渉する確率が相対的に高いことを示している一方、経路２００ｂ上の動的障害物２０は現実に存在しており確実に干渉することを意味しているからである。言い換えれば、経路２００ａと経路２００ｂとでは、動的障害物と干渉する確率が経路２００ａの方が小さいと言える。
【００４２】
なお、経路２００ｂ上に動的障害物２０が検出された場合に経路２００ａを最適経路として選択するのではなく、動的障害物２０の障害の確率を定量的に評価し、当該評価結果に応じて最適経路を選択してもよい。
【００４３】
具体的には、経路２００ｂ上に動的障害物２０が検出された場合、自走式画像形成装置１２は、スタート地点Ｓから動的障害物２０までの距離を検出し、距離に応じて動的障害物２０の障害の確率を評価する。例えば、
障害の確率＝１／距離
として評価する。この式は、距離が近いほど障害の程度が大きい、つまり動的障害物２０と干渉する可能性が高いことを意味している。自走式画像形成装置１２は、ある一定の速度以下で自走するから、動的障害物２０までの距離が大きいほど、その動的障害物２０の存在位置に達するまで時間を要し、この時間内において動的障害物２０が移動して経路２００ｂから外れる可能性がある。自走式画像形成装置１２は、経路２００ａにおける障害物情報から算出した障害の確率と、動的障害物２０までの距離から算出した障害の確率を比較考量し、動的障害物２０までの距離が小さくその障害の確率が大きい場合には経路２００ａを選択し、逆に、動的障害物２０までの距離が大きくその障害の確率が小さい場合には動的経路２００ｂを選択する。
【００４４】
もちろん、上記の処理を簡易化し、自走式画像形成装置１２がしきい距離Ｌを記憶し、動的障害物２０までの距離がしきい距離Ｌ以下であれば経路２００ａを選択し、しきい距離Ｌを超える場合には経路２００ｂを選択してもよい。
【００４５】
＜本実施形態の構成＞
次に、本実施形態の具体的な構成について説明する。
【００４６】
図８に、本実施形態における自走式画像形成装置１２の構成図を示す。自走式画像形成装置１２は、障害物蓄積情報管理部３０と、マップ（Ｍａｐ）管理部３２と、経路計画装置３４と、走行制御装置３６と、ユーザインタフェース３８と、非接触型障害物検知装置４０と、接触型障害物検知装置４２と、アクチュエータ４４を備える。
【００４７】
障害物蓄積情報管理部３０は、過去の障害物蓄積情報５０を記憶・管理する。障害物蓄積情報管理部３０は、障害物蓄積情報５０を経路計画装置３４に供給する。
【００４８】
マップ（Ｍａｐ）管理部３２は、マップ情報５２を記憶・管理する。マップ情報５２には、マップＡｂｓｔ情報及びマップレイアウト情報が含まれる。マップＡｂｓｔ情報は、類似するレイアウトを同一のものとして認識するための情報である。マップレイアウト情報は、静的障害物のマップ情報である。マップ管理部３２は、マップ情報５２を経路計画装置３４に供給する。
【００４９】
経路計画装置３４は、マップ管理部３２からのマップ情報５２と、障害物蓄積情報管理部３０からの障害物蓄積情報５０とに基づいて、スタート地点Ｓからゴール地点Ｇに到達するための経路を探索する。経路計画装置３４は、探索した経路を走行制御装置３６に供給する。
【００５０】
走行制御装置３６は、経路計画装置３４で探索して得られた経路に沿って自走すべく、アクチュエータ４４に駆動信号を出力する。
【００５１】
アクチュエータ４４は、走行モータ、ブレーキ及び操舵モータ等から構成され、走行制御装置３６からの駆動信号に基づいて駆動され、自走式画像形成装置１２を自走させる。
【００５２】
非接触型障害物検知装置４０は、カメラや赤外線センサ、超音波センサ等であり、動的障害物を検知して障害物蓄積情報管理部３０及び経路計画装置３４に供給する。検知された動的障害物は、障害物蓄積情報５０の一つとして障害物蓄積情報管理部３０に記憶される。また、検知された動的障害物は、経路計画装置３４において障害の度合い等が評価されて経路探索に用いられる。
【００５３】
接触型障害物検知装置４２は、自走している間に障害物を検知して走行制御装置３６に供給する。
【００５４】
ユーザインタフェース３８は、利用者やカフェ１０の客に対して自走式画像形成装置１２の状態を報知するためのものである。自走中はライトを点灯させる他、客に経路から外れてもらいたい場合にその旨のメッセージを報知する。
【００５５】
自走式画像形成装置１２は、これら以外に、画像データを受信する手段、画像データを印刷する手段、印刷した画像を出力する手段等を備えるが、これらは画像形成装置として公知の構成であるためその説明は省略する。
【００５６】
また、図８では、自走式画像形成装置１２が障害物蓄積情報管理部３０を備え、障害物蓄積情報５０を記憶・管理するとしているが、これに代えて、カフェ１０のサーバが障害物蓄積情報５０を記憶・管理し、必要に応じて自走式画像形成装置１２の経路計画装置３４に供給する構成としてもよい。マップ（Ｍａｐ）管理部３２についても同様である。
【００５７】
障害物蓄積情報管理部３０及びマップ管理部３２は、メモリで構成され、経路計画装置３４及び走行制御装置３６はコンピュータ、より特定的にはＣＰＵやＭＰＵ等のプロセッサで構成される。
【００５８】
図９に、障害物蓄積情報５０の一例を示す。障害物蓄積情報５０は、マップ１６のグリッド毎に管理される。障害物蓄積情報５０は、月日、曜日、時間帯、催し、遭遇回数から構成される。ここで、「催し」は、カフェ１０において特定のイベントがあった場合に登録される。また、「遭遇回数」は、過去に遭遇した総回数を意味する。図９に示す障害物蓄積情報５０は、あるグリッドにおいて、６月１日火曜日の８：００〜１０：００において、特定のイベントがなく合計１２３回動的障害物が存在したことを示している。
【００５９】
図１０に、マップ情報５２と障害物蓄積情報５０との関係を示す。マップ情報５２には、マップＡｂｓｔ５２ａが含まれ、それぞれのマップＡｂｓｔ５２ａにはマップレイアウト５２ｂが含まれる。マップレイアウト５２ｂは、静的障害物の配置を示すマップであり、異なるマップレイアウト５２ｂは静的障害物の配置が異なることを示す。例えば、あるカフェＡにおいて静的障害物の配置が異なるいくつかのパターンが存在する場合、これらはマップレイアウト１、マップレイアウト２、・・・等と分類される。同じカフェである以上、多少マップレイアウトが異なっていても互いに類似するマップレイアウトである、マップＡｂｓｔ５２ａは、このように互いに類似するマップレイアウトをひとまとめにしたマップである。もちろん、同じカフェでも静的障害物の配置は大きく異なる場合もあり得るが、この場合、別のマップＡｂｓｔ５２ａとして登録される。それぞれのマップレイアウト５２ｂ毎に、障害物蓄積情報５０が登録される。すなわち、マップレイアウト１に対して複数の障害物蓄積情報５０が登録され、マップレイアウト２に対して複数の障害物蓄積情報５０が登録される。図９に即して説明すると、カフェ１０の静的障害物の配置を示す特定のマップレイアウトが示され、このマップレイアウトのそれぞれのグリッドに障害物蓄積情報５０が登録されている。
【００６０】
図１１に、障害物蓄積情報５０の詳細をさらに示す。マップレイアウトＩＤ、セグメントＩＤ、年月日、曜日、時間帯、イベント、動的障害物検知回数がそれぞれ規定される。図において、セグメントＩＤは、マップレイアウトを構成するグリッドを特定するＩＤであり、例えばセグメントＩＤが（１，１）は、ｘ−ｙ２次元直交座標における（ｘ、ｙ）＝（１，１）のグリッドを示す。
【００６１】
また、図において、セグメントＩＤ＝（１，１）のグリッドに関し、２０１２年９月３日の１０：００〜１１：００にはイベントとして「パーティ」が規定されている。これは、当該曜日の当該時間にパーティが開かれたことを意味しており、このときの動的障害物検知回数は５回であることを示す。経路計画装置３４は、障害物蓄積情報５０を用いて経路探索するが、経路探索時において当該グリッドでイベントがあればこの障害物蓄積情報５０における動的障害物検知回数の５回を用いるが、当該グリッドでイベントがない場合には条件が異なるためこの障害物蓄積情報５０における動的障害物検知回数の５回は採用しない。
【００６２】
＜本実施形態の経路探索処理＞
図１２に、本実施形態における経路探索（経路計画）処理のフローチャートを示す。経路計画装置３４で実行される処理であり、ＲＯＭ等のプログラムメモリその他の媒体に記憶されたプログラムを読み出して実行することで経路探索処理が実現される。プログラムは、ファームウェアとして当初からプログラムメモリに記憶されていてもよいが、ネットワークを介してインストールしてもよく、あるいはＣＤやＤＶＤ等の可搬性記録媒体にプログラムを記録し、この可搬性記録媒体からインストールしてもよい。
【００６３】
まず、経路計画装置３４は、マップ管理部３２にアクセスし、対応するマップレイアウトＮを取得する（Ｓ１０１）。対応するマップレイアウトＮとは、自走式画像形成装置１２が自走しようとするカフェ１０のレイアウトに合致するマップレイアウトである。
【００６４】
次に、経路計画装置３４は、マップレイアウトＮを用いて静的障害物と干渉しないようなルートを作成する（Ｓ１０２）。マップレイアウトＮの各グリッドには動的障害物蓄積情報５０が含まれているが、ここでは動的障害物蓄積情報５０をひとまず無視してルートを作成する。作成したルートをルート１，ルート２，ルート３等とする。作成したルートは、一旦ワーキングメモリに記憶する。
【００６５】
次に、経路計画装置３４は、現在時刻における動的障害物蓄積情報を取得する（Ｓ１０３）。すなわち、非接触型障害物検知装置４０によりルート上の動的障害物を検知し、検知した動的障害物情報を入力する。あるいは、カフェ１０の所定位置に設置されたセンサにより動的障害物を検知し、検知した動的障害物情報を入力する。障害物情報には、その動的障害物の位置、すなわちグリッドが含まれる。経路計画装置３４は、現在の動的障害物情報を取得すると、取得した情報を用いてマップ管理部３２に記憶されている動的障害物蓄積情報５０を更新する（Ｓ１０４）。具体的には、図１１に示す動的障害物蓄積情報５０において、新たに取得された動的障害物情報を用いて対応するセグメントＩＤ（グリッドＩＤ）の項目を更新する。例えば、セグメントＩＤ＝（１，１）の動的障害物検知回数を２から３に更新する、セグメントＩＤ＝（１，４）の動的障害物検知回数を０から１に更新する等である。
【００６６】
次に、経路計画装置３４は、マップ管理部３２にアクセスし、マップＡｂｓｔＮから類似する障害物蓄積情報をまとめて取得する（Ｓ１０５）。例えば、Ｓ１０１で取得したマップレイアウトＮがマップＡｂｓｔ１に属し、このマップＡｂｓｔにはマップレイアウトＮ以外にマップレイアウト１，２が含まれている場合、マップレイアウト１，２に含まれる障害物蓄積情報５０を全て取得する（図１０を参照）。
【００６７】
次に、経路計画装置３４は、取得した全ての動的障害物蓄積情報をマージし（Ｓ１０６）、さらに、マージした全ての動的障害物蓄積情報をマップレイアウトＮにマージする（Ｓ１０７）。すなわち、全ての動的障害物蓄積情報をマップレイアウトＮの対応するグリッドに追加する。
【００６８】
次に、経路計画装置３４は、Ｓ１０２で作成した全てのルートをワーキングメモリから読み出して取得し（Ｓ１０８）、全てのルートに対して動的障害物遭遇確率を計算する（Ｓ１０９）。具体的には、あるルートの遭遇確率を計算する際に、そのルート上にある全てのグリッドの動的障害物蓄積情報５０を読み出し、曜日、時間帯、イベント、遭遇回数のそれぞれの項目を重み付けして計算する。例えば、曜日が一致する場合には係数＝１とし、曜日が一致しない場合には係数＝０．５とする。また、時間帯が一致する場合には係数＝１とし、時間帯が一致しない場合には係数＝０．５とする。イベントが一致する場合には係数＝１とし、一致しない場合には係数＝０．５とする。これらの係数を乗算し、得られた係数で遭遇回数を評価して確率を計算する。なお、本実施形態における「確率」は、確からしさの度合いを示す指標として定義されており、必ずしも０と１の間の値である必要はなく、定量評価できる任意の指標を用い得る。例えば、ルート上のグリッド（ｘ、ｙ）の遭遇回数が５であり、曜日、時間帯、イベントが一致する場合には、
確率＝１×１×１×５＝５
となる。一方、曜日、時間帯、イベントのいずれも一致しない場合には
確率＝０．５×０．５×０．５×５＝０．６２５
となる。ルート上の全てのグリッドについて同様の計算を行い、その中で最も高い確率をそのルートの遭遇確率とする。もちろん、この算出は一例にすぎず、他の算出方法を用いてもよい。また、最も高い確率をそのルートの遭遇確率とするのではなく、そのルート上の全ての確率を加算してそのルートの遭遇確率としてもよい。さらに、算出した遭遇確率を０と１の間の値に正規化してもよい。以下では、遭遇確率を０と１の間に正規化したものとして説明する。
【００６９】
全てのルートについて動的障害物蓄積情報５０を用いて遭遇確率を計算した後、経路計算装置３４は、遭遇確率が最低のルートを最適ルートとして選択する（Ｓ１１０）。この際、ルート上に現在動的障害物が存在する場合には、そのルートの障害物確率を最大値の１として計算する。例えば、Ｓ１０８で取得したルートがルート１、ルート２、ル−ト３の３つのルートが存在し、それぞれの遭遇確率として
ルート１：０．９
ルート２：０．５
ルート３：０
と計算されたものとする。この場合、遭遇確率が最低のルートはルート３であるため、経路計画装置３４はル−ト３を選択する。他方、非接触型障害物検知装置４０でルート３上のいずれかのグリッドに動的障害物が検知されている場合、あるいはカフェ１０の所定位置に設置されたセンサでルート３上のいずれかのグリッドに動的障害物が検知されている場合、ルート３の遭遇確率は１とされるため、遭遇確率が最低のルートはルート２となるため、経路計画装置３４はルート２を選択する。
【００７０】
このように、本実施形態の処理では、遭遇確率の相対的な大小関係を用いるため、遭遇確率の絶対値は本質的ではなく、この意味で遭遇確率は必ずしも０と１の間である必要はないことが理解されよう。遭遇確率を０と１の間に正規化しない場合、ルート上に現在動的障害物が存在する場合にそのルートの障害物確率を１とする代わりに、所定の最大値を設定することは言うまでもない。
【００７１】
また、経路計画装置３４は、遭遇確率が最低のルートが複数存在する場合には、ゴールまでの距離が最短のルートを最適経路として選択する（Ｓ１１１）。例えば、
ルート１：０．５
ルート２：０．５
ルート３：１
であり、最低の遭遇確率のルートとしてルート１、ルート２が存在する場合、ゴールまでの距離が
ルート１：１０ｍ
ルート２：２０ｍ
であれば、ルート１を最適ルートとして選択する。
ルートを選択した後、経路計画装置３４は、走行制御装置３６に対して移動開始指示を出力する（Ｓ１１２）。走行制御装置３６は、この指示に従い、選択したルートに沿って自走すべくアクチュエータ４４に制御信号を出力する。ルートに沿って自走中に、接触型障害物検知装置４２で障害物を検知した場合、走行制御装置３６は自走を停止し、所定時間だけ待機する、あるいはルート上から外れてもらうようなメッセージを報知する等の特定の処理を実行する。ゴールに到達した場合、走行制御装置３６は自走を停止し、図示しない画像形成手段にゴールに到達した旨の信号を出力する。
【００７２】
なお、Ｓ１１１において、現在動的障害物が検出されたルートの遭遇確率を１としたが、既述したように、現在動的障害物が存在するグリッドの位置に応じて遭遇確率を変化させてもよく、動的障害物までの距離が小さいほど遭遇確率を大きく設定した上で、最低の遭遇確率となるルートを選択してもよい。要するに、過去に動的障害物が存在したルートは、そうでないルートに比べて選択の優先順位を低下させ、現に動的障害物が存在するルートは、過去に動的障害物が存在したルートに比べて選択の優先順位を低下させ、あるいは、現に動的障害物が存在するルートは、動的障害物までの距離に応じ、距離が小さいほど選択の優先順位を低下させればよい。これにより、過去に動的障害物が存在しないルートを優先的に選択するようになり、また、たとえ過去に動的障害物が存在したとしても現に動的障害物が存在するルートに比べてそのルートを優先的に選択するようになる。
【００７３】
＜他の実施形態＞
上記の実施形態では、自走式画像形成装置１２がスタート地点Ｓに存在しているときにゴール地点Ｇまでの経路を探索し、最適経路を選択して自走する場合について説明したが、最適経路を選択してゴールに向かって自走している間に、経路上に動的障害物が偶発的に出現する場合もあり得る。本実施形態では、このような場合の処理について説明する。
【００７４】
図１３に、本実施形態における処理フローチャートを示す。まず、経路計画装置３４及び走行制御装置３６は、選択した計画経路に沿った移動を行う（Ｓ２０１）。計画経路は、図１２に示したフローチャートに従って選択された経路である。
【００７５】
次に、非接触型障害物検知装置４０は、ルート上をスキャンして動的障害物を検知する（Ｓ２０２）。この処理は、カフェ１０の所定位置に設置されたセンサを用いて実行してもよい。そして、ルート上に動的障害物が検知されたか否かを判定する（Ｓ２０３）。
【００７６】
移動しているルート上に動的障害物が存在しない場合（Ｓ２０３でＮＯ）、そのまま移動を継続する。
【００７７】
他方、移動しているルート上に動的障害物を検知した場合（Ｓ２０３でＹＥＳ）、経路計画装置３４は、ルート上の現在位置からそれ以上進むと後戻りが必要になるか否かを判定する（Ｓ２０４）。この判定は、ルートを探索する際に用いたマップレイアウトＮの静的障害物の配置を用いて行う。
【００７８】
後戻りが必要でないと判定された場合（Ｓ２０４でＮＯ）、そのまま移動を継続する。
【００７９】
他方、後戻りが必要になると判定された場合、経路計画装置３４は、その時点を新たなスタート地点としてゴールまでの新たな経路を図１２に示すフローチャートを用いて再度探索する（Ｓ２０５）。
【００８０】
図１４〜図１６を用いて、本実施形態の処理をさらに説明する。
【００８１】
図１４に、図１２に示すフローチャートに従って、経路計画装置３４がゴールに至る経路を選択した時点の状況を示す、自走式画像形成装置１２がスタート地点Ｓに位置し、ゴール地点Ｇに至る経路として経路３００が示されている。この状況を時刻ｔ０とする。
【００８２】
図１５に、時刻ｔ０から時間が進んだ、時刻ｔ１における状況を示す、自走式画像形成装置１２が、経路３００に沿って自走して時刻ｔ１において一定の位置まで移動する。この時点で、経路３００上に動的障害物２０が検知されたものとする。この場合、経路３００上に新たに動的障害物２０が検知されたからといって、一律に経路を再探索するリルート処理を行う構成では、動的障害物２０が検知される度に新た経路を探索し、探索して得られた経路に沿って自走することになるため、結局、ゴールに到達するまで時間を要してしまい効率的でない。
【００８３】
そこで、たとえ自走している間に動的障害物２０が偶発的に出現しても、後戻りするしか選択肢がなくなるまで、元の経路３００に沿ってそのまま移動を継続する。但し、図１５に示すように、そのまま経路３００上を移動して時刻ｔ２となり、後戻りするしか選択肢がなくなると、結局、その時点でリルートして元来た経路を戻る必要が生じてしまう。
【００８４】
これに対し、図１６に示すように、それ以上進むと元来た経路を後戻りするしか選択肢がなくなる位置まで移動する。この時刻をｔ３とする。そして、時刻ｔ３においてリルートし、ゴール地点Ｇに到達できる経路を再探索する。この場合、後戻りする経路ではないため、その分だけ到達時間が短縮される。図において、再探索して得られた経路は経路４００として示されている。経路を再探索する際に、動的障害物２０が存在する元の経路３００に関しては、その遭遇確率が１に設定されているため、再探索において最適経路として選択されることはない。図１５における経路３００と、図１６における経路４００を比較すれば、経路４００の優位性は明らかであろう。
【００８５】
このように、本実施形態では、自走している間にその経路上に動的障害物２０が出現しても、その時点でリルートするのではなく、それ以上進むと後戻りするしか選択肢がなくなる位置までは元の経路をそのまま進み、それ以上進むと後戻りするしか選択肢がなくなる位置まで到達した時点でリルートを行うため、効率的にリルートが行われる。また、動的障害物が出現する度にその都度リルートを行わないため、頻繁にリルートが行われて結局ゴール地点Ｇに到達するまでに時間を要する問題を回避し得る。また、本実施形態では、それ以上進むと後戻りするしか選択肢がなくなる位置までは元の経路をそのまま進むため、その間に動的障害物２０が経路から外れることも期待され、この場合には元の経路をそのまま移動してゴール地点Ｇに到達し得る。
【００８６】
なお、本実施形態において、動的障害物２０が検知された時点において、既に自走式画像形成装置１２が後戻りするしか選択肢がない位置にいる場合には、動的障害物２０に対して経路から外れるように依頼するメッセージを報知すればよい。
【００８７】
図１７に、この状況を示す。自走式画像形成装置１２が経路３００に沿って移動し、時刻ｔ２において動的障害物２０を検知したものの、その時点においては迂回路がなく、元来た経路を後戻りするしか選択肢がない。そこで、経路計画装置３４は、ユーザインタフェース３８から「少し移動して下さい。」等のメッセージを出力する。
【００８８】
以上、本発明の実施形態について説明したが、本発明はこれらの実施形態に限定されるものではなく、種々の変形が可能である。
【００８９】
例えば、本実施形態では自走式作業装置として自走式画像形成装置１２を例示したが、画像形成以外の任意の作業を行うことができる。また、必ずしも車両形態である必要はなく、広くロボット一般に適用し得る。この場合、自走式作業装置は、自走式ロボットと言い換えることができよう。
【００９０】
また、図１７において動的障害物２０（多くの場合は人であろう）に対してメッセージを報知して経路から外れてもらうように依頼したが、経路計画装置３４はマップ情報５２及び自走する経路情報を有しているので、これらに基づいて動的障害物２０に対してどこに移動するように依頼してもよい。例えば、自走式画像形成装置１２から見て動的障害物２０の左側に静的障害物が存在し、右側にはスペースがあってルート上でない場合には、「少し右側に移動して下さい」等のメッセージをユーザインタフェース３８から出力してもよい。あるいは、ユーザインタフェース３８を液晶画面等とし、この画面上に自己のゴール地点Ｇを表示して、動的障害物２０に対して自己がどの位置に向かっているかを明確に示すことも好適であろう。もちろん、所定時間（例えば３０秒間）だけその場で待機し、動的障害物２０の状況を確信した後でメッセージを報知してもよい。待機中は、待機中である旨のメッセージをユーザインタフェース３８に表示することが好適である。
【符号の説明】
【００９１】
１０  カフェ、１２  自走式画像形成装置、１４  自走可能領域、３０  障害物蓄積情報管理部、３２  マップ管理部、３４  経路計画装置、３６  走行制御装置、３８  ユーザインタフェース、４０  非接触型障害物検知装置、４２  接触型障害物検知装置、４４  アクチュエータ、５０  障害物蓄積情報、５２  マップ情報。
【図１】
2014209293.tif 000003
【図２】
2014209293.tif 000004
【図３】
2014209293.tif 000005
【図４】
2014209293.tif 000006
【図５】
2014209293.tif 000007
【図６】
2014209293.tif 000008
【図７】
2014209293.tif 000009
【図８】
2014209293.tif 000010
【図９】
2014209293.tif 000011
【図１０】
2014209293.tif 000012
【図１１】
2014209293.tif 000013
【図１２】
2014209293.tif 000014
【図１３】
2014209293.tif 000015
【図１４】
2014209293.tif 000016
【図１５】
2014209293.tif 000017
【図１６】
2014209293.tif 000018
【図１７】
2014209293.tif 000019