図面 (/)

技術 情報処理装置、情報処理システム、移動経路決定方法及びプログラム

出願人 株式会社リコー国立大学法人鳥取大学
発明者 岡本敏弘工藤宏一横田孝義田村翼
出願日 2017年2月10日 (5年0ヶ月経過) 出願番号 2017-023585
公開日 2018年8月16日 (3年6ヶ月経過) 公開番号 2018-129000
状態 特許登録済
技術分野 移動体の位置、進路、高度又は姿勢の制御
主要キーワード スマート端末 最小移動量 最大ステップ 干渉箇所 ネットワーク形状 干渉度合い 移動終了位置 自立移動
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2018年8月16日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (20)

課題

動体全体での移動経路がより好適化されるように、移動体間での干渉を回避させることができる情報処理装置情報処理システム、移動経路決定方法及びプログラムを提供することを目的とする。

解決手段

複数の移動体それぞれの移動経路を生成する生成部151と、複数の移動体による複数の移動経路の移動に伴い、複数の移動体のうちの少なくとも2以上の移動体間で干渉が発生するか否かを判定する判定部153と、干渉が発生する場合、2以上の移動体のうちの一方の移動体を移動経路上で一時的に待機させることで干渉を回避させるよう当該移動経路を更新する更新部155と、を備える。

概要

背景

従来から、複数の移動体で複数の地点巡回させるための最適経路を求める手法として、探索的な手法(例えば、遺伝的アルゴリズム)など種々の手法が提案されている。

また、例えば特許文献1には、干渉度合い評価関数とした評価指標に基づいて、複数の移動体で複数の地点を巡回させるための最適経路を作成し、作成した最適経路において移動体間干渉が生じなくなるまで、評価指標を変更して最適経路を再作成する手法が提案されている。

概要

移動体全体での移動経路がより好適化されるように、移動体間での干渉を回避させることができる情報処理装置情報処理システム、移動経路決定方法及びプログラムを提供することを目的とする。複数の移動体それぞれの移動経路を生成する生成部151と、複数の移動体による複数の移動経路の移動に伴い、複数の移動体のうちの少なくとも2以上の移動体間で干渉が発生するか否かを判定する判定部153と、干渉が発生する場合、2以上の移動体のうちの一方の移動体を移動経路上で一時的に待機させることで干渉を回避させるよう当該移動経路を更新する更新部155と、を備える。

目的

本発明は、上記事情に鑑みてなされたものであり、移動体全体での移動経路がより好適化されるように、移動体間での干渉を回避させることができる情報処理装置、情報処理システム、移動経路決定方法及びプログラムを提供する

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

複数の移動体それぞれの移動経路を生成する生成部と、前記複数の移動体による前記複数の移動経路の移動に伴い、前記複数の移動体のうちの少なくとも2以上の移動体間干渉が発生するか否かを判定する判定部と、前記干渉が発生する場合、前記2以上の移動体のうちの一方の移動体を移動経路上で一時的に待機させることで前記干渉を回避させるよう当該移動経路を更新する更新部と、を備える情報処理装置

請求項2

前記生成部は、複数のノードとノード間を接続するアークとで構成される1層のネットワーク上で、前記複数の移動経路を生成し、前記更新部は、前記1層のネットワークを複層化したネットワークであって、前記干渉が生じるノード及びアークへの進入禁止された複層のネットワーク上で、前記干渉を回避させるよう、前記一方の移動体の移動経路を更新する請求項1に記載の情報処理装置。

請求項3

前記複層のネットワークは、2層のネットワークである請求項2に記載の情報処理装置。

請求項4

前記待機は、前記複層のネットワークにおける層間の移動で表される請求項2又は3に記載の情報処理装置。

請求項5

前記更新部は、前記複層のネットワーク上で、前記干渉を回避させるよう、前記一方の移動体の移動経路を更新できない場合、前記複層のネットワークの層数を増やして、前記干渉を回避させるよう、前記一方の移動体の移動経路を更新する請求項1に記載の情報処理装置。

請求項6

前記判定部は、前記複数の移動経路の単位移動量毎に、前記複数の移動体のうちの少なくとも2以上の移動体間で干渉が発生するか否かを判定し、前記更新部は、前記干渉が発生する場合、前記2以上の移動体のうちの一方の移動体を移動経路上で一時的に待機させることで前記干渉を回避させるよう当該移動経路を更新する請求項1に記載の情報処理装置。

請求項7

前記更新部は、前記待機により前記干渉を回避できない場合、前記2以上の移動体のうちの一方の移動体を迂回させることで前記干渉を回避させるよう当該移動経路を更新する請求項6に記載の情報処理装置。

請求項8

情報処理装置と複数の出力装置とを備える情報処理システムであって、前記情報処理装置は、複数の移動体それぞれの移動経路を生成する生成部と、前記複数の移動体による前記複数の移動経路の移動に伴い、前記複数の移動体のうちの少なくとも2以上の移動体間で干渉が発生するか否かを判定する判定部と、前記干渉が発生する場合、前記2以上の移動体のうちの一方の移動体を移動経路上で一時的に待機させることで前記干渉を回避させるよう当該移動経路を更新する更新部と、前記複数の出力装置それぞれに、当該出力装置に対応付けられた移動体の移動経路を示す移動経路情報を送信する送信部と、を備え、前記複数の出力装置それぞれは、前記情報処理装置から送信された前記移動経路情報が示す移動経路を出力する情報処理システム。

請求項9

複数の移動体それぞれの移動経路を生成する生成ステップと、前記複数の移動体による前記複数の移動経路の移動に伴い、前記複数の移動体のうちの少なくとも2以上の移動体間で干渉が発生するか否かを判定する判定ステップと、前記干渉が発生する場合、前記2以上の移動体のうちの一方の移動体を移動経路上で一時的に待機させることで前記干渉を回避させるよう当該移動経路を更新する更新ステップと、を含む移動経路決定方法

請求項10

複数の移動体それぞれの移動経路を生成する生成ステップと、前記複数の移動体による前記複数の移動経路の移動に伴い、前記複数の移動体のうちの少なくとも2以上の移動体間で干渉が発生するか否かを判定する判定ステップと、前記干渉が発生する場合、前記2以上の移動体のうちの一方の移動体を移動経路上で一時的に待機させることで前記干渉を回避させるよう当該移動経路を更新する更新ステップと、をコンピュータに実行させるためのプログラム

技術分野

背景技術

0002

従来から、複数の移動体で複数の地点巡回させるための最適経路を求める手法として、探索的な手法(例えば、遺伝的アルゴリズム)など種々の手法が提案されている。

0003

また、例えば特許文献1には、干渉度合い評価関数とした評価指標に基づいて、複数の移動体で複数の地点を巡回させるための最適経路を作成し、作成した最適経路において移動体間干渉が生じなくなるまで、評価指標を変更して最適経路を再作成する手法が提案されている。

発明が解決しようとする課題

0004

しかしながら、上述したような従来技術では、経路変更により移動体間での干渉の発生を回避している。つまり上述したような従来技術では、移動体間での干渉の発生を迂回により回避することになるため、干渉の発生を回避した経路が移動体の移動距離移動時間の観点から、好適であるとは限らない。

0005

本発明は、上記事情に鑑みてなされたものであり、移動体全体での移動経路がより好適化されるように、移動体間での干渉を回避させることができる情報処理装置、情報処理システム、移動経路決定方法及びプログラムを提供することを目的とする。

課題を解決するための手段

0006

上述した課題を解決し、目的を達成するために、本発明の一態様にかかる情報処理装置は、複数の移動体それぞれの移動経路を生成する生成部と、前記複数の移動体による前記複数の移動経路の移動に伴い、前記複数の移動体のうちの少なくとも2以上の移動体間で干渉が発生するか否かを判定する判定部と、前記干渉が発生する場合、前記2以上の移動体のうちの一方の移動体を移動経路上で一時的に待機させることで前記干渉を回避させるよう当該移動経路を更新する更新部と、を備える。

発明の効果

0007

本発明によれば、移動体全体での移動経路がより好適化されるように、移動体間での干渉を回避させることができるという効果を奏する。

図面の簡単な説明

0008

図1は、第1実施形態の情報処理システムの構成の一例を示すブロック図である。
図2は、第1実施形態の情報処理装置のハードウェア構成の一例を示すブロック図である。
図3は、第1実施形態の情報処理装置の機能構成の一例を示すブロック図である。
図4は、第1実施形態の情報処理システムで行われる移動経路生成処理の一例を示すフローチャートである。
図5は、第1実施形態のネットワーク構成の一例の説明図である。
図6は、補助記憶装置対応付け登録されたノードのID、ロボットのID、及び経由時刻の一例の説明図である。
図7は、第1実施形態の干渉判定手法の一例の説明図である。
図8は、第1実施形態の干渉判定手法の一例の説明図である。
図9は、第1実施形態の干渉判定手法の一例の説明図である。
図10は、第1実施形態の干渉判定手法の一例の説明図である。
図11は、第1実施形態の干渉判定手法の一例の説明図である。
図12は、第1実施形態の情報処理装置で行われる移動経路決定処理の一例を示すフローチャートである。
図13は、第2実施形態の情報処理装置の機能構成の一例を示すブロック図である。
図14は、第2実施形態の干渉判定手法の一例の説明図である。
図15は、第2実施形態の干渉判定手法の一例の説明図である。
図16は、第2実施形態の干渉判定手法の一例の説明図である。
図17は、第2実施形態の移動経路更新手法の一例の説明図である。
図18は、第2実施形態の移動経路更新手法の一例の説明図である。
図19は、第2実施形態の移動経路更新手法の一例の説明図である。
図20は、第2実施形態の移動経路更新手法の一例の説明図である。
図21は、第2実施形態の移動経路更新手法の一例の説明図である。
図22は、第2実施形態の移動経路更新手法の一例の説明図である。
図23は、第2実施形態の移動経路更新手法の一例の説明図である。
図24は、第2実施形態の情報処理装置10で行われる移動経路決定処理の一例を示すフローチャートである。

実施例

0009

以下、添付図面を参照しながら、本発明にかかる情報処理装置、情報処理システム、移動経路決定方法及びプログラムの実施形態を詳細に説明する。

0010

以下の各実施形態では、移動路上に存在する複数の地点を複数の移動体で巡回させるための、各移動体の移動経路における移動体間の干渉回避を例に取り説明するが、これに限定されるものではない。具体的には、移動路は倉庫内の移動路であり、移動路上に存在する複数の地点は、倉庫内に分散して保管された複数の商品が配置されている地点であり、複数の移動体は、当該複数の商品を収集ピッキング)するために倉庫内に分散して配置されたロボット(カート)であり、倉庫内に保管された複数の商品を複数台のロボットでピッキングするピッキング作業を例に取り説明するが、これに限定されるものではない。より詳細には、倉庫内の移動路は、複数のノードと当該ノード間を接続するアークとで構成されるネットワーク状の経路であり、商品及びロボットは、いずれかのノードに配置されている場合を想定して説明するが、これに限定されるものではない。なお、このようなネットワーク形状の経路の場合、ロボット間の干渉は、2つ以上のロボットが同一のノードに同時に進入する場合、及び2つ以上のロボットが同一のアーク上ですれ違う場合の2パターンが挙げられる。また以下の各実施形態では、ロボット(カート)は、自動で自立移動する移動体である場合を例に取り説明するが、これに限定されず、ユーザにより手動で移動されるロボット(カート)であってもよい。

0011

(第1実施形態)
図1は、第1実施形態の情報処理システム1の構成の一例を示すブロック図である。図1に示すように、情報処理システム1は、情報処理装置10と、端末装置20と、出力装置30−1〜30−n(nは2以上の自然数)と、を備える。情報処理装置10、端末装置20、及び出力装置30−1〜30−nは、ネットワーク2を介して接続されている。ネットワーク2は、例えば、インターネットやLAN(Local Area Network)などにより実現できる。なお、以下の説明では、出力装置30−1〜30−nを各々区別する必要がない場合は、単に出力装置30と称する場合がある。

0012

情報処理装置10は、移動路上に存在する複数の商品を複数のロボットで巡回して収集するための、当該複数のロボットそれぞれの移動経路を生成及び更新するものであり、例えば、1台以上のコンピュータにより実現できる。

0013

図2は、第1実施形態の情報処理装置10のハードウェア構成の一例を示すブロック図である。情報処理装置10は、CPU(Central Processing Unit)やGPU(Graphics Processing Unit)などの制御装置101と、ROM(Read Only Memory)やRAM(Random Access Memory)などの主記憶装置102と、HDD(Hard Disk Drive)やSSD(Solid State Drive)などの補助記憶装置103と、ディスプレイなどの表示装置104と、キーボードマウスなどの入力装置105と、通信インタフェースなどの通信装置106と、を備えており、通常のコンピュータを利用したハードウェア構成となっている。

0014

端末装置20は、情報処理装置10に対し、収集対象の複数の商品を指定するものであり、例えば、PC(Personal Computer)やスマート端末などが挙げられる。

0015

出力装置30は、情報処理装置10により決定された移動経路を出力するものである。なお第1実施形態では、各出力装置30は、ロボットに対応付けられており(備え付けられており)、当該ロボット用の移動経路を出力する。出力装置30は、例えば、ロボットに備え付けられたディスプレイやスピーカ、ロボットをユーザが移動させる場合には、当該ユーザが所持するスマート端末などが挙げられる。なお、移動経路の出力は、表示出力音声出力投影出力、及び印刷出力などどのような出力態様で行われても構わない。

0016

図3は、第1実施形態の情報処理装置10の機能構成の一例を示すブロック図である。図3に示すように、情報処理装置10は、生成部151と、判定部153と、更新部155と、送信部157と、を含む。生成部151及び送信部157は、例えば、制御装置101、主記憶装置102、及び通信装置106などにより実現できる。判定部153、及び更新部155は、例えば、制御装置101及び主記憶装置102などにより実現できる。

0017

生成部151は、複数の移動体それぞれの移動経路を生成する。第1実施形態では、生成部151は、移動路上に存在する複数の商品を複数のロボットで巡回して収集するための、当該複数のロボットそれぞれの移動経路を生成する。なお第1実施形態では、生成部151は、複数のノードとノード間を接続するアークとで構成される1層のネットワーク上で、複数の移動経路を生成する。

0018

1層のネットワークは、例えば、図5に示すネットワーク構成のFirst layerのネットワークが挙げられる。なお、図5に示すネットワーク構成のSecond layerのネットワークについては、後述する。また、図5に示すネットワーク構成では、点がノードを表し、点間を接続する線がアークを表している。なお、第1実施形態では、アークで接続されたノード間の距離が1であるものとする。

0019

第1実施形態では、どのような手法で複数のロボットの移動経路を生成しても構わないが、生成に要する時間が短く、かつ、移動経路全体での移動時間(移動距離)をできるだけ短くできるような手法であることが好ましい。このため、上記のような条件を満たす移動経路生成用のアルゴリズムを用いて移動経路を生成することが好ましいが、生成時間の制約さえ満たせば、遺伝的アルゴリズムを用いて移動経路を生成しても構わない。なお、各移動体の移動速度は、一定の速度に固定されていることを前提とする。

0020

図4は、第1実施形態の情報処理システム1で行われる移動経路生成処理の一例を示すフローチャートである。なお、図4に示すフローチャートは、上記のような条件を満たす移動経路生成用のアルゴリズムによる移動経路生成処理のフローチャートである。このアルゴリズムによれば、生成に要する時間が短く、かつ、全体での移動時間(移動距離)をできるだけ短くできる移動経路を生成できる。

0021

まず、移動経路の生成に先立ち、生成部151は、複数のロボットそれぞれの移動開始位置情報移動終了位置情報、複数のロボットにより収集される複数の商品それぞれの収集対象物位置情報、及び移動路情報を取得する(ステップS101)。

0022

移動開始位置情報は、ロボットの移動開始位置を示し、移動終了位置情報は、ロボットの移動終了位置を示し、収集対象物位置情報は、商品の位置を示し、移動路情報は、ロボットが移動可能な移動路(前述のネットワーク)を示す。

0023

続いて、生成部151は、取得した複数の移動開始位置情報、複数の移動終了位置情報、複数の収集対象物位置情報、及び移動路情報に基づいて、商品毎に、複数のロボットそれぞれについて、当該ロボットが移動路を移動して、移動開始位置から当該商品を収集して移動終了位置に到達するまでに要する最小移動量を算出する(ステップS103)。

0024

第1実施形態では、最小移動量及び後述の移動量が時間である場合を例に取り説明するが、これに限定されず、距離としてもよい。また第1実施形態では、最小移動量の算出は、例えば、ダイクストラー法やA*スター法などの公知技術を用いて行えばよい。また、最小移動量での移動経路が複数存在する場合、全移動経路を求めておくものとする。

0025

続いて、生成部151は、複数の商品のうち最小移動量の最小値が最大となる商品を、複数のロボットのうち、当該商品の収集に要する最小移動量が最小となるロボットに割り当てる(ステップS105)。

0026

続いて、生成部151は、当該割り当てたロボットが当該商品を最小移動量で収集して移動終了位置に最小移動量で到達するための移動経路上に、収集するロボットに割り当てられていない商品があれば、当該収集するロボットに割り当てられていない商品を当該割り当てたロボットに更に割り当てる(ステップS107)。

0027

続いて、収集するロボットに割り当てられていない商品が残っており(ステップS109でYes)、生成部151は、残っている1以上の商品のうち最小移動量の最小値が最大となる商品の収集に要する最小移動量が最小となるロボットが未割り当てであれば(ステップS111でYes)、当該ロボットに当該最小移動量の最小値が最大となる商品を割り当てる(ステップS113)。そして、ステップS107へ戻る。

0028

一方、生成部151は、残っている1以上の商品のうち最小移動量の最小値が最大となる商品の収集に要する最小移動量が最小となるロボットが未割り当てでなければ(ステップS111でNo)、分散度合いを判定する判定式を満たし、かつ商品が割り当てられていない1以上のロボットがあれば(ステップS115でYes)、当該1以上のロボットのうち、当該最小移動量の最小値が最大となる商品の収集に要する最小移動量が最小となるロボットに当該最小移動量の最小値が最大となる商品を割り当てる(ステップS117)。そして、ステップS107へ戻る。

0029

分散度合いを判定する判定式としては、ロボットXと商品Qとの最小移動量=ロボットXとロボットYとの距離+ロボットYと商品Qとの最小移動量が挙げられるが、これに限定されるものではない。なお、ロボットXが判定式を満たすか否かの対象となるロボットであり、商品Qが割り当て対象の商品であり、ロボットYが任意のロボットである。

0030

上述の判定式を満たす場合、ロボットXとロボットYとの配置が局所的であると判定され、ロボットXとロボットYをグループとして包含関係にあると認識する。そして、この場合、商品Qは、ロボットYではなく、ロボットXに割り当てられるため、ロボットYに偏って商品が割り当てられてしまうことを防止できる。

0031

なお、生成部151は、分散度合いを判定する判定式を満たし、かつ商品が割り当てられていない1以上のロボットがなければ(ステップS115でNo)、複数のロボットのうち、残っている1以上の商品のうち最小移動量の最小値が最大となる商品の収集に要する最小移動量が最小となり、かつ移動量が最小のロボットに、移動量の増加が最小となるように、当該最小移動量の最小値が最大となる商品を割り当てる(ステップS119)。そして、ステップS107へ戻る。

0032

なお、ステップS119の処理については、残っている1以上の商品のうち最小移動量の最小値が最大となる商品との移動路上での距離が最も短い商品を収集するロボットに、移動量の増加が最小となるように、当該最小移動量の最小値が最大となる商品を割り当てるようにしてもよい。

0033

また、ステップS119の処理については、残っている1以上の商品のうち最小移動量の最小値が最大となる商品と移動路上で最も近接する1以上のロボットのうち、移動量が最小のロボットに、移動量の増加が最小となるように、当該最小移動量の最小値が最大となる商品を割り当てるようにしてもよい。

0034

ステップS109において、収集するロボットに割り当てられていない商品が残っていない場合(ステップS109でNo)、生成部151は、割り当て結果に基づいて、複数のロボットの移動経路を生成する(ステップS121)。

0035

判定部153は、複数の移動体による複数の移動経路の移動に伴い、当該複数の移動体のうちの少なくとも2以上の移動体間で干渉が発生するか否かを判定する。具体的には、判定部153は、複数のロボットによる複数の移動経路の移動に伴い、当該複数のロボットのうちの少なくとも2以上のロボット間で、同一のノードに同時に進入することがあるか、及び同一のアーク上ですれ違うことがあるかを判定する。判定部153は、2以上のロボット間で、同一のノードに同時に進入する、又は同一のアーク上ですれ違う場合には、2以上のロボット間で、干渉が発生すると判定する。

0036

更新部155は、判定部153により干渉が発生すると判定された場合、2以上の移動体のうちの一方の移動体を移動経路上で一時的に待機させることで干渉を回避させるよう当該移動経路を更新する。

0037

具体的には、更新部155は、生成部151による複数のロボットそれぞれの移動経路の生成に使用された1層のネットワークを複層化したネットワークであって、干渉が生じるノード及びアークへの進入が禁止された複層のネットワーク上で、干渉を回避させるよう、一方のロボットの移動経路を更新する。なお、移動経路上でのロボットの待機は、層間の移動で表され、詳細には、1層の移動が1ステップの待機(距離1の移動に要する時間分の待機)に該当する。第1実施形態では、複層のネットワークは、2層のネットワークである場合を例に取り説明するが、これに限定されるものではない。

0038

図5に示す例の場合であれば、生成部151は、First layerのネットワークで、各ロボットの移動経路を生成したが、更新部155は、判定部153により干渉が発生すると判定された場合、First layerのネットワークをSecond layerのネットワークで複層化した2層のネットワーク上で、干渉を回避させるよう、一方のロボットの移動経路を更新する。より詳細には、更新部155は、First layerのネットワーク上の干渉が生じるノード及びアークへの進入を禁止し、かつ、First layerのネットワークからSecond layerのネットワークへの移動は可能であるが、Second layerのネットワークからFirst layerのネットワークへの移動は不可能というルールの元、一方のロボットの移動経路を更新する。

0039

また、更新部155は、移動経路を更新する場合、例えば、ダイクストラー法やA*スター法など、移動時間や移動距離が最小となる移動経路を算出可能な公知技術を用いて行えばよい。一般的に、ダイクストラー法やA*スター法などのアルゴリズムでは、同一ノードに留まることや戻ることはできないが、第1実施形態のように、ネットワークを複層化することで、同一ノード上に待機することを層間の移動で表すことができる。

0040

つまり、上述のように、干渉が生じるノード及びアークへの進入を禁止し、かつ、複層化したネットワーク上で、ダイクストラー法やA*スター法などを用いて、一方のロボットの移動経路を更新することで、干渉箇所を迂回で回避する移動経路や干渉箇所を待機で回避する移動経路の中から、移動時間や移動距離が最小となる移動経路を算出することができる。

0041

なお、干渉箇所を迂回で回避する場合、少なくとも2ステップ以上の偶数ステップの回避行動が必要となるが(2ステップ以上の偶数ステップ分、移動時間や移動距離が増加するが)、干渉箇所を待機で回避する場合、1ステップからの回避行動が可能となる。このため、干渉箇所を迂回のみで回避するのではなく、少なくとも待機も用いて回避する方が、移動経路の移動時間や移動距離を短くでき、移動経路を好適化できる。

0042

以下、干渉を回避するように移動経路を更新して、各ロボットの移動経路を決定する手法について具体的に説明する。

0043

判定部153は、生成部151により生成された各移動経路優先順位を設定して、優先順位の順に干渉判定を行いながら、移動経路を決定する。なお、優先順位は、どのような手法で決定してもよく、その手法は問わない。

0044

まず、判定部153は、優先順位の最も高い移動経路について、当該移動経路を構成する各ノードのIDに、当該優先順位の最も高い移動経路を移動するロボットのID、及び当該ノードをロボットが経由する時刻を対応付けて、補助記憶装置103に登録(記憶)する。なお、判定部153は、優先順位の最も高い移動経路については、干渉判定無しに移動経路を決定する。

0045

続いて、判定部153は、優先順位が2番目に高い移動経路についても、当該移動経路を構成する各ノードのIDに、当該優先順位の最も高い移動経路を移動するロボットのID、及び当該ノードをロボットが経由する時刻を対応付けて、補助記憶装置103に登録(記憶)する。

0046

図6は、補助記憶装置103に対応付けて登録されたノードのID、ロボットのID、及び経由時刻の一例の説明図である。図6に示す例では、ロボットのIDが「Robot1」のロボットの移動経路が、優先順位が最も高い。「Robot1」のロボットの移動経路は、ノードのIDが「Node[i][j]」、「Node[i][j+1]」のノードで構成されており、「Node[i][j]」には、「Robot1」及び経由時刻(Time)「0」、「Node[i][j+1]」には、「Robot1」及び経由時刻(Time)「1」が対応付けられている。つまり、「Robot1」のロボットは、Time「0」の時点では、Node[i][j]のノードに位置し、Time「1」の時点では、Node[i][j+1]のノードに位置するように移動することがわかる。

0047

また、図6に示す例では、ロボットのIDが「Robot2」のロボットの移動経路が、優先順位が2番目に高い。「Robot2」のロボットの移動経路は、ノードのIDが「Node[i][j+2]」、「Node[i][j+1]」のノードで構成されており、「Node[i][j+2]」には、「Robot2」及び経由時刻(Time)「1」、「Node[i][j+1]」には、「Robot2」及び経由時刻(Time)「2」が対応付けられている。つまり、「Robot2」のロボットは、Time「1」の時点では、Node[i][j+2]のノードに位置し、Time「2」の時点では、Node[i][j+1]のノードに位置するように移動することがわかる。

0048

そして判定部153は、優先順位が2番目に高い移動経路については、補助記憶装置103に対応付けて登録されたノードのID、ロボットのID、及び経由時刻を用いて、「Robot1」のロボット及び「Robot2」のロボット間での干渉判定を行う。

0049

具体的には、判定部153は、優先順位が2番目に高い移動経路(「Robot2」のロボットの移動経路)を構成する各ノードにおいて、「Robot2」のロボットと「Robot1」のロボットとが同一時刻に位置するか否かを判定する。この条件を満たす場合には、同一のノードに同時に進入することになるため、判定部153は、「Robot2」のロボットが、「Robot1」のロボットに干渉すると判定する。

0050

また、判定部153は、優先順位が2番目に高い移動経路(「Robot2」のロボットの移動経路)を構成する連続する2つのノードの各組において、一方のノードには、「Robot2」が時刻tの時点、「Robot1」が時刻t+1の時点で位置するとともに、他方のノードには、「Robot1」が時刻t+1の時点、「Robot1」が時刻tの時点で位置するかを判定する。この条件を満たす場合には、同一のアーク上ですれ違うことになるため、判定部153は、「Robot2」のロボットが、「Robot1」のロボットに干渉すると判定する。

0051

そして更新部155は、判定部153により、「Robot1」のロボット及び「Robot2」のロボット間での干渉が発生すると判定された場合、上述の手法で、干渉を回避するように、「Robot2」のロボットの移動経路を更新し、判定部153は、「Robot2」のロボットの移動経路を決定する。

0052

以下、優先順位の高い移動経路の順に上述の処理を繰り返し、各ロボットの移動経路を決定する。

0053

なお、ネットワークを2層化した場合、判定部153は、1層目のネットワークだけでなく、2層目のネットワークにおいても、干渉判定を行うことが必要であるが、補助記憶装置103に対応付けて登録されたノードのID、ロボットのID、及び経由時刻の情報が1層目のネットワーク上での情報に該当するため、この情報を1ステップ分遅らせた情報を2層目のネットワーク上での情報として用いて、干渉判定を行えばよい。

0054

また、干渉を回避するために待機を行うタイミングについては、種々のタイミングが可能となることも考えられるが(例えば、1ステップ目で待機してもよいし、2ステップ目で待機してもよいなど)、移動経路の移動時間や移動距離をできるだけ短くする観点から、出来るだけ干渉が発生する直前のタイミングで待機することが好ましい。

0055

例えば、図7に示すようなケースを考える。図7に示す例では、ロボットAは、AからA’に移動し、ロボットBは、BからB’に移動し、ロボットCは、CからC’に移動するものとする。なお、丸がノードを示し、線がアークを示す。この場合、各ロボットの干渉を考慮しない移動経路は、図8に示すとおりとなり、4ステップ目において、ノード13でロボットAとロボットBの干渉が発生する。

0056

ここで、干渉が発生する直前の3ステップ目でロボットAを待機させて干渉を回避する場合、図9に示すとおりとなり、各ロボットの移動経路の最大ステップは7ステップとなる。

0057

一方、スタート時点の1ステップ目でロボットAを待機させて干渉を回避する場合、図10に示すように、ノード13でのロボットAとロボットBの干渉は回避できているが、3ステップ目において、ノード3でロボットAとロボットCの新たな干渉が発生してしまう。このため、スタート時点の1ステップ目でロボットCも待機させて新たな干渉も回避する場合、図11に示すとおりとなり、各ロボットの移動経路の最大ステップは8ステップとなる。

0058

このように、干渉が発生する直前のタイミングで待機を行う方が、新たな干渉の発生確率を抑えられるため、移動経路の移動時間や移動距離をできるだけ短くする観点から、できるだけ干渉が発生する直前のタイミングで待機することが好ましい。

0059

送信部157は、判定部153により各移動体の移動経路が決定されると、移動体毎に、当該移動体に対応付けられた出力装置30に当該移動体の移動経路を示す移動経路情報を送信する。

0060

各出力装置30は、情報処理装置10から送信された移動経路情報が示す移動経路を出力する。

0061

図12は、第1実施形態の情報処理装置10で行われる移動経路決定処理の一例を示すフローチャートである。

0062

まず、生成部151は、移動路上に存在する複数の商品を複数のロボットで巡回して収集するための、当該各ロボットの移動経路(但し、ロボット間の干渉の発生は考慮しない)を生成する(ステップS10)。

0063

続いて、判定部153は、生成部151により生成された各移動経路に優先順位を設定する(ステップS20)。

0064

続いて、判定部153は、全てのロボットの干渉判定が終了していなければ(ステップS30でNo)、干渉の判定対象のロボットを更新する(ステップS40)。なお、この更新は、移動経路の優先順位の高い順に行われる。

0065

続いて、判定部153は、判定対象のロボットで干渉が発生するか否かを判定する(ステップS50)。なお、判定対象のロボットが、優先順位が最も高い移動経路を移動するロボットである場合、干渉は発生しないと判定され、判定対象のロボットが、優先順位が2番目に高い移動経路を移動するロボットである場合、優先順位が最も高い移動経路を移動するロボットとの間で干渉が発生するか否かが判定され、判定対象のロボットが、優先順位が3番目に高い移動経路を移動するロボットである場合、優先順位が最も高い移動経路を移動するロボット及び優先順位が2番目に高い移動経路を移動するロボットとの間で干渉が発生するか否かが判定される。

0066

続いて、判定部153は、判定対象のロボットで干渉が発生しないと判定した場合(ステップS50でNo)、当該判定対象のロボットの移動経路を決定(確定)し、ステップS30へ戻る。

0067

一方、判定部153は、判定対象のロボットで干渉が発生すると判定した場合(ステップS50でYes)、干渉が生じるノード及びアークへの進入が禁止された2層のネットワーク上で、干渉を回避させるよう、当該判定対象のロボットの移動経路を更新することで決定(確定)し(ステップS60)、ステップS30へ戻る。

0068

そして判定部153は、全てのロボットの干渉判定が終了し(ステップS30でYes)、全てのロボットの移動経路を決定すれば、処理を終了する。

0069

以上のように第1実施形態によれば、干渉箇所を迂回だけでなく待機により回避するため、移動体全体での移動経路がより好適化されるように、移動体間での干渉を回避させることができる。

0070

なお第1実施形態では、複層のネットワークが2層のネットワークである場合を例に取り説明したが、これに限定されず、3層以上のネットワークであってもよい。特に、更新部155は、複層のネットワーク上で、干渉を回避させるよう、一方の移動体の移動経路を更新できない場合、複層のネットワークの層数を増やして、干渉を回避させるよう、一方の移動体の移動経路を更新するようにしてもよい。

0071

複数台のロボットが同時刻に局所的に集中する場合、ロボット間の干渉頻度が増加するが、このような状況下においては、迂回や1ステップの待機では、干渉を回避できない、即ち、移動経路を生成(更新)できない可能性がある。このため、更新部155は、移動経路を生成できない(更新できない)場合、移動経路を生成できるまで、層数を1増やして(1ステップ分余剰に待機可能にして)、移動経路の生成処理を行うようにしてもよい。このようにすれば、移動経路をいずれ生成できるので、移動経路を生成できないという事態の発生を回避できる。

0072

また第1実施形態では、2層のネットワークにおいて、First layerのネットワークからSecond layerのネットワークへの移動は可能であるが、Second layerのネットワークからFirst layerのネットワークへの移動は不可能というルールを例に取り説明したが、Second layerのネットワークからFirst layerのネットワークへの移動も可能としてもよい。このようにすれば、層間の往復移動が可能になるので、層数を増やさなくても、2ステップ分以上の待機を表すことが可能となる。

0073

(第2実施形態)
第1実施形態では、移動体単位で干渉を判定する例について説明したが、第2実施形態では、ステップ単位で干渉を判定する例について説明する。なお以下では、第1実施形態との相違点の説明を主に行い、第1実施形態と同様の機能を有する構成要素については、第1実施形態と同様の名称・符号を付し、その説明を省略する。

0074

図13は、第2実施形態の情報処理装置1010の機能構成の一例を示すブロック図である。図13に示すように、第2実施形態の情報処理装置1010では、判定部1153及び更新部1155が第1実施形態と相違する。

0075

判定部1153は、複数の移動経路の単位移動量毎に、複数の移動体のうちの少なくとも2以上の移動体間で干渉が発生するか否かを判定する。第2実施形態では、判定部1153は、各ロボットの移動経路の移動ステップ毎に、複数のロボットのうちの少なくとも2以上のロボット間で干渉が発生するか否かを判定する。

0076

更新部1155は、判定部1153により干渉が発生すると判定された場合、2以上の移動体のうちの一方の移動体を移動経路上で一時的に待機させることで干渉を回避させるよう当該移動経路を更新する。また更新部1155は、待機により干渉を回避できない場合、2以上の移動体のうちの一方の移動体を迂回させることで干渉を回避させるよう当該移動経路を更新する。第2実施形態では、更新部1155は、判定部1153により干渉が発生すると判定された場合、2以上のロボットのうちの一方のロボットを移動経路上で一時的に待機させることで干渉を回避させるよう当該移動経路を更新し、待機により干渉を回避できない場合、当該一方のロボットを迂回させることで干渉を回避させるよう当該移動経路を更新する。

0077

例えば、図14に示すようなケースを考える。図14に示す例では、ロボットAは、商品αを収集して元の位置へ戻る、ロボットBは、商品βを収集して元の位置へ戻る、ロボットCは、商品γを収集して元の位置へ戻るものとする。なお、丸がノードを示し、線がアークを示す。この場合、各ロボットの干渉を考慮しない移動経路は、図15に示すとおりとなり、判定部1153は、ステップ毎に干渉判定を行う。なお第2実施形態では、判定部1153は、移動経路のステップ数が少ない順(移動時間や移動距離が長い順)に優先順位を設定する。なお第2実施形態では、数値が高いほど優先順位(Priority)が高いものとする。

0078

そして判定部1153は、干渉が発生しなければ、該当ステップでの各ロボットの移動経路を決定(確定)し、干渉が発生する場合、更新部1155は、干渉が発生するロボットのうち優先順位が低い方のロボットの移動経路を更新し、判定部1153は、干渉判定をやり直す。

0079

なお、図15に示す例では、ノード19でロボットAとロボットBの干渉(同時進入)が発生するため、判定部1153は、2ステップ目の干渉判定において、ノード19でロボットAとロボットBの干渉が発生すると判定する。

0080

また、図16に示す例は、各ロボットの干渉を考慮しない他の移動経路の例であるが、ノード19とノード20を接続するアークでロボットBとロボットDの干渉(すれ違い)が発生するため、2ステップ目の干渉判定において、ノード19とノード20を接続するアークでロボットBとロボットDの干渉が発生すると判定する。

0081

以下、干渉を回避させるための移動経路の更新手法について説明する。

0082

第2実施形態では、更新部1155は、干渉が発生する場合、ステップ数を増加させずに干渉を回避するよう移動経路を更新、待機により干渉を回避するよう移動経路を更新、及び迂回により干渉を回避するよう移動経路を更新のいずれかの手法で、干渉を回避する。

0083

例えば、図14及び図15に示す例の場合、前述したように、ノード19でロボットAとロボットBの干渉(同時進入)が発生する。ここで、優先順位の高いロボットAについては、ステップ数を増加させずに干渉を回避することができない。一方、優先順位の低いロボットBについては、現状、「17⇒18⇒19⇒20⇒21⇒14⇒21⇒20⇒19⇒18⇒17」であるが、「17⇒10⇒11⇒12⇒13⇒14⇒13⇒12⇒11⇒10⇒17」という移動経路であれば、ステップ数を増加させずに干渉を回避することができる。

0084

このため、更新部1155は、図17に示すように、ロボットBの移動経路を「17⇒10⇒11⇒12⇒13⇒14⇒13⇒12⇒11⇒10⇒17」に更新し、判定部1153は、ロボットBの移動経路については、更新後の移動経路で、ステップ毎に干渉判定を行う。

0085

また例えば、図18に示すようなケースを考える。図18に示す例では、ロボットAは、Aからαに移動し、ロボットBは、Bからβに移動する。なお、丸がノードを示し、線がアークを示す。この場合、各ロボットの干渉を考慮しない移動経路は、図19に示すとおり、ロボットAは、6⇒7⇒8⇒9⇒4⇒5、ロボットBは、2⇒3⇒4⇒9⇒14となる。この場合、ノード9でロボットAとロボットBの干渉(同時進入)が発生する。

0086

ここで、優先順位の高いロボットB及び優先順位の低いロボットAの双方ともステップ数を増加させずに干渉を回避することができない。このため、優先順位の高いロボットBについて、待機、進行方向に対し左右、後方順序で移動可能か判定し、移動経路を更新する。この例では、待機により干渉を回避可能な移動経路に更新可能であるため、更新部1155は、例えば、ダイクストラー法やA*スター法などにより、図20に示すように、ロボットBの移動経路を「2⇒3⇒3⇒8⇒9⇒14」に更新し、判定部1153は、ロボットBの移動経路については、更新後の移動経路で、ステップ毎に干渉判定を行う。

0087

また例えば、図21に示すようなケースを考える。図21に示す例では、ロボットAは、Aからαに移動し、ロボットBは、Bからβに移動する。なお、丸がノードを示し、線がアークを示す。この場合、各ロボットの干渉を考慮しない移動経路は、図22に示すとおり、ロボットAは、1⇒2⇒3⇒4⇒、ロボットBは、3⇒2となる。この場合、ノード2でロボットAとロボットBの干渉(同時進入)が発生する。

0088

ここで、優先順位の高いロボットB及び優先順位の低いロボットAの双方ともステップ数を増加させずに干渉を回避することができない。このため、優先順位の高いロボットBについて、待機、進行方向に対し左右、後方の順序で移動可能か判定し、移動経路を更新する。この例では、待機では干渉を回避できないが、進行方向に対し左に移動することで干渉を回避可能な移動経路に更新できるため、更新部1155は、例えば、ダイクストラー法やA*スター法などにより、図23に示すように、ロボットBの移動経路を「3⇒8⇒7⇒2」に更新し、判定部1153は、ロボットBの移動経路については、更新後の移動経路で、ステップ毎に干渉判定を行う。

0089

図24は、第2実施形態の情報処理装置1010で行われる移動経路決定処理の一例を示すフローチャートである。

0090

まず、生成部151は、移動路上に存在する複数の商品を複数のロボットで巡回して収集するための、当該各ロボットの移動経路(但し、ロボット間の干渉の発生は考慮しない)を生成する(ステップS1010)。

0091

続いて、判定部1153は、生成部151により生成された各移動経路に優先順位を設定する(ステップS1020)。

0092

続いて、判定部1153は、全ての移動ステップで干渉判定が終了していなければ(ステップS1030でNo)、干渉の判定対象の移動ステップを更新する(ステップS1040)。なお、この更新は、移動ステップをインクリメントすることで行われる。

0093

続いて、判定部1153は、判定対象の移動ステップにおいて、各ロボット間に干渉が発生するか否かを判定する(ステップS1050)。なお、判定対象の移動ステップにおいて、各ロボット間に干渉が発生しない場合(ステップS1050でNo)、ステップS1030へ戻る。

0094

一方、判定対象の移動ステップにおいて、各ロボット間に干渉が発生する場合(ステップS1050でYes)、判定部1153は、干渉が発生するロボット間において、優先順位の高い順に、ステップ数を増加させずに干渉を回避するよう移動経路を更新できるか否かを判定する(ステップS1060)。

0095

ステップ数を増加させずに干渉を回避するよう移動経路を更新できる場合(ステップS1060でYes)、更新部1155は、そのように移動経路を更新し(ステップS1070)、ステップS1020へ戻る。なお、ステップS1020へ戻った場合、判定部1153は、更新後の移動経路を採用して、優先順位を設定し直し、ステップ毎の干渉判定も最初からやり直す。

0096

一方、ステップ数を増加させずに干渉を回避するよう移動経路を更新できない場合(ステップS1060でNo)、更新部1155は、干渉が発生するロボットのうち優先順位の高い方のロボットについて、待機、進行方向に対し左右、後方の順序で次に移動するノードを決定し(ステップS1080)、目的地までの移動経路を再探索する(ステップS1090)。そして、目的地までの移動経路を再探索、即ち、生成できた場合(ステップS1100でYes)、当該移動経路に更新して、ステップS1020へ戻る。なお、ステップS1020へ戻った場合、判定部1153は、更新後の移動経路を採用して、優先順位を設定し直し、ステップ毎の干渉判定も最初からやり直す。

0097

つまり、ステップS1080では、最初に待機で次に移動するノードを決定し、目的地までの移動経路を生成できなければ(ステップS1100でNo)、次に進行方向に対して左右で次に移動するノードを決定し、目的地までの移動経路を生成できなければ、最後に進行方向に対して後方で次に移動するノードを決定し、目的地までの移動経路を生成する。

0098

以上のように第2実施形態においても、干渉箇所を迂回だけでなく待機により回避するため、移動体全体での移動経路がより好適化されるように、移動体間での干渉を回避させることができる。

0099

(変形例)
上記実施形態では、倉庫内でのカートを用いて商品を(ピッキング)収集したり、カートを用いて商品を格納する場合を例に取り説明した。

0100

但し、これに限定されず、コミュニティバスによる人間の送迎などにも応用できる。この場合、移動体はコミュニティバスとなり、移動路上に存在する複数の地点は、人間がいる場所や人間を送る場所となり、移動路は道路となる。

0101

また、物資救援救護搬送などの災害対応計画などにも応用できる。この場合、移動体は自動車となり、移動路上に存在する複数の地点は、被災者、物資、病院、及び避難所がある場所となり、移動路は道路となる。

0102

また、集荷配達などの宅配などにも応用できる。この場合、移動体はトラックとなり、移動路上に存在する複数の地点は、宅配物がある場所や居所などとなり、移動路は道路となる。

0103

また、営業マンの巡回などにも応用できる。この場合、移動体は自動車となり、移動路上に存在する複数の地点は、営業マンがいる場所や訪問先などとなり、移動路は道路となる。

0104

また、移動体を自動車とする場合、出力装置30をカーナビゲーションプロジェクタとしてもよい。出力装置30がプロジェクタの場合、移動経路を自動車のフロントガラス投影するなどの態様が考えられる。

0105

(プログラム)
上記実施形態及び各変形例の情報処理装置10で実行されるプログラムは、インストール可能な形式又は実行可能な形式のファイルCD−ROM、CD−R、メモリカード、DVD(Digital Versatile Disk)、フレキシブルディスクFD)等のコンピュータで読み取り可能な記憶媒体に記憶されて提供される。

0106

また、上記実施形態及び各変形例の情報処理装置10で実行されるプログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するようにしてもよい。また、上記各実施形態及び各変形例の情報処理装置10で実行されるプログラムを、インターネット等のネットワーク経由で提供または配布するようにしてもよい。また、上記各実施形態及び各変形例の情報処理装置10で実行されるプログラムを、ROM等に予め組み込んで提供するようにしてもよい。

0107

上記実施形態及び各変形例の情報処理装置10で実行されるプログラムは、上述した各部をコンピュータ上で実現させるためのモジュール構成となっている。実際のハードウェアとしては、例えば、CPUがROMからプログラムをRAM上に読み出して実行することにより、上記各機能部がコンピュータ上で実現されるようになっている。

0108

なお、上記実施形態及び各変形例は、例として提示したものであり、発明の範囲を限定することは意図していない。上記新規な実施の形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これらの実施の形態は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。

0109

1情報処理システム
2ネットワーク
10、1010情報処理装置
20端末装置
30−1〜30−n(30)出力装置
151 生成部
153、1153 判定部
155、1155更新部
157 送信部

先行技術

0110

特許第4138541号公報

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

該当するデータがありません

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

該当するデータがありません

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ