JPH10247112A - 移動体割当て方法 - Google Patents

Abstract

(57)【要約】 【課題】 要求元からの要求に対して、移動体を効率よ
く割り当てることができる移動体割り当て方法を提供す
る。 【解決手段】 所定領域を複数の区域に分割して、各区
域ごとに管制センターを配置し、区域内での割当てをそ
の区域に所属する管制センターが行ない、要求元からの
割当て要求に対して、その所属する区域内に割当て可能
な移動体がなければ、予め他の管制センターのそれぞれ
について設定された宛先選択率に基づいて、移動体を要
求する管制センターを決定し、その決定した管制センタ
ーに対して、移動体要求メッセージを放送し、その管制
センターとの間で、入札メッセージ及び落札メッセージ
のやり取りを行い、移動体の割当てを行うようにした。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、自律移動ロボット
や無人搬送車などの複数の移動体を複数の要求元に繰り
返し割当てる移動体割当て方法に関するものである。

【０００２】

【従来の技術】従来、自律移動ロボットや無人搬送車な
どの移動体を要求元に繰り返し割当てる移動体割当て方
法を適用したシステムとしては、例えば、工場や物流タ
ーミナルなどにおける荷物搬送システムがあった。これ
は、倉庫や出入荷場や建物で生じる荷物の運搬要求に対
して、適当な無人搬送車を割当て、荷物を運搬するシス
テムである。

【０００３】従来のこのようなシステムでは、一つの管
制センタ、複数の移動体及び複数の要求元で構成され、
各構成要素は適当な通信手段を有し、お互いにメッセー
ジ交換をすることができるようになっている。そして、
各移動体は、目的地を指示すれば、自律的に目的地まで
移動することが可能である。また、管制センタは、領域
内の割当て可能なすべての移動体の現在位置を獲得可能
であり、地図データにより、領域内の任意の２点間の距
離を知ることができるようになっている。

【０００４】そして、要求元への移動体の割当てには、
以下に示すような方法がとられていた。まず、移動体の
割当てを受けたい要求元は、管制センタに対して割当て
要求を発行する。そして、管制センタでは、要求元から
の割当て要求を受信すると、その要求元に最近距離にあ
る移動体に移動指示を出す。そして、管制センタからの
移動指示を受けとった移動体は、その移動指示により指
定された要求元まで移動する。このようにして、要求元
への移動体の割当てが完了する。

【０００５】

【発明が解決しようとする課題】しかしながら、従来の
移動体割当て方法では、管制センタにおいて、すべての
移動体の位置を管理し、移動体と要求元の可能な組合せ
すべての中から最適なものを選択するようになってお
り、そのため、移動体と要求元の数が比較的多く大規模
なシステムでは、多くの処理を必要とし、リアルタイム
での制御が困難になるという問題点があった。

【０００６】

【課題を解決するための手段】本発明に係る移動体割当
て方法は、所定領域内に複数の移動体及びその移動体の
割当てを要求する複数の要求元を存在させ、移動体の割
当てを要求した複数の要求元に対して複数の移動体を繰
り返し割当てる移動体割当て方法において、所定領域を
複数の区域に分割して、各区域ごとに管制センタを配置
し、区域内に存在する要求元及び移動体を、その区域に
所属する要求元及び移動体とし、移動体の割当てを受け
たい要求元では、その要求元が所属する区域の管制セン
タに対して割当て要求を発行し、割当て要求を受けとっ
た管制センタでは、その所属する区域内に割当て可能な
移動体があれば、その移動体の中から割当て要求を発行
した要求元に最近距離にある移動体を選択し、その選択
した移動体に対して移動指示を発行して、移動体の割当
てを行ない、その所属する区域内に割当て可能な移動体
がなければ、予め他の管制センタのそれぞれについて設
定された宛先選択率に基づいて、移動体を要求する管制
センタを決定し、その決定した管制センタに対して、移
動体要求メッセージを発行し、その移動体要求メッセー
ジを受けとった管制センタでは、その管制センタの所属
する区域内の移動可能な移動体の位置及び識別子を付加
した入札メッセージを、移動要求メッセージを発行した
管制センタに対して発行し、管制センタからの入札メッ
セージを受けとった管制センタでは、その入札メッセー
ジに付加された移動体の情報に基づいて、割当て要求を
発行した要求元に近い移動体を順に必要数だけ選択し
て、その移動体の識別子及び割当て要求を発行した要求
元の位置を付加した落札メッセージを、選択した移動体
の所属する管制センタに対して発行し、その落札メッセ
ージを受けとった管制センタでは、その落札メッセージ
に付加された識別子の移動体に対して、割当て要求を発
行した要求元への移動指示を発行して、移動体の割当て
を行うものである。

【０００７】

【発明の実施の形態】

実施の形態１．図２は、本発明の移動体割当て方法を説
明するための説明図であり、この実施の形態の移動体割
当て方法を適用する移動体割当てシステムの一構成例を
示している。

【０００８】この移動体割当てシステムは、図２に示す
ように、移動体の移動エリア内を、仮想的に複数の区域
に分割しておき、各区域に一ずつの管制センタを配置し
ている。また、移動体の移動エリア内には、複数の移動
体及び複数の要求元が存在しており、各移動体及び各要
求元は、それぞれある区域内に入っているときにその区
域に所属している状態となる。そして、管制センタ、移
動体及び要求元は、適当な通信手段を有しており、お互
いにメッセージ交換をすることができるようになってい
る。

【０００９】また、移動体は目的地を指示すれば、その
目的地に自律的に移動することができるようになってお
り、各管制センタは、その管制センタの区域内に所属し
ている移動体の位置を獲得できるようになっている。そ
して、この移動体の位置は、各管制センタによって連続
的に絶えず獲得するようにしてもよいし、所定時間間隔
で獲得するようにしてもよい。また、各要求元は、自己
の位置を取得するなどして、その所属している区域を獲
得できるようになっている。

【００１０】なお、移動体の移動エリア内における区域
の分け方に特に制限はないが、例えば、複数の建物から
なる工場では一つの建物を一つの区域とすればよいし、
超高層ビルなら連続する数階分のフロアを一つの区域と
すればよい。

【００１１】次に、この実施の形態の動作について説明
する。図１は、この実施の形態の動作を説明するための
説明図である。図において、図１の（ａ）は、要求元の
所属区域内に割当て可能な移動体がいる場合の動作を示
し、図１の（ｂ）は、要求元の所属区域内に割当て可能
な移動体がいない場合の動作を示している。

【００１２】まず、各移動体からは、その移動体が所属
している区域の管制センタに対して自分の位置に関する
情報や、移動可能な状態であるかなどを送信しており、
管制センタは、その所属区域に所属している移動体の状
態を把握しているものとする（１１，２１）。そして、
移動体の割当てを受けたい要求元は、要求元が所属する
区域の管制センタに対して割当て要求を発行する（１
２、２２）。

【００１３】そして、割当て要求を受けとった管制セン
タは、その所属区域内に割当て可能な移動体があれば、
その中から要求元に最近距離にある移動体に移動指示を
出し（１３）、移動指示を受けとった移動体が、指定さ
れた要求元まで移動して、割当てが完了する（１４）。

【００１４】また、割当て要求を受けとった管制センタ
の所属区域内に割当て可能な移動体がなければ、管制セ
ンタ間で、次に示すようなメッセージ交換を行ない、他
の区域から移動体を移動させて割当てを行なう。まず、
割当て要求を受けとった管制センタは、その管制センタ
が持っている宛先選択率に従って確率的に決められた管
制センタの宛先を、移動体要求メッセージの宛先として
付加し、その宛先の管制センタに対して、移動体要求メ
ッセージを発行する（２３）。

【００１５】この宛先選択率は、総和が１となるよう
な、他の管制センタの個数分の数字の組からなるもので
ある。そして、この宛先選択率の値は、あらかじめシス
テムの設計者が、システムの形態に応じて、ヒューリス
ティックに決定するものであり、移動体割当てシステム
を模擬できるシミュレータがあれば、候補となるいくつ
かの組み合わせで評価を行い、待ち時間の最小化など、
システムの目的関数をより最適化する組を採用すればよ
い。

【００１６】例えば、１０個の管制センタ（Ａ₀ ，
Ａ₁ ，…，Ａ₉ ）から成るシステムで、管制センタＡ₀
からは、Ａ₁ ，Ａ₂ ，…，Ａ₉ の順で距離が短いとす
る。このとき設計者が、距離の近い上位４管制センタに
等確率で移動体要求メッセージを発行する、というよう
に決めれば、宛先選択率は以下に示すようになる。 （0.25,0.25,0.25,0.25,0,0,0,0,0 ）

【００１７】そして、このような宛先選択率の場合、移
動体が１つ必要なときには、管制センタＡ₁ ，Ａ₂ ，Ａ
₃ ，Ａ₄ に対する宛先選択率は同じなので、等確率で管
制センタＡ₁ ，Ａ₂ ，Ａ₃ ，Ａ₄ の内の１つの管制セン
タが宛先として選択され、その管制センタに対して移動
体要求メッセージを発行することになる。

【００１８】また、複数の移動体が同時に必要であれ
ば、宛先選択率に従って、複数の移動体のそれぞれにつ
いて、移動体の要求先の管制センタを１つずつ決定す
る。その結果、１つの管制センタに複数の要求を発行す
ることになれば、その管制センタへの移動体要求メッセ
ージにその要求数を付加する。

【００１９】そして、その管制センタからの移動体要求
メッセージを受けとった他の管制センタは、移動体要求
メッセージを発行した管制センタに対して、入札メッセ
ージを発行する（２４）。この入札メッセージには、移
動体要求メッセージを受けとった管制センタの所属区域
内に存在する移動可能な移動体の識別子及び位置を付加
する。このとき、ある管制センタが移動体要求メッセー
ジを複数の管制センタから受けとっていた場合には、各
移動体要求メッセージに付加された要求数の比に、移動
可能な移動体を振り分けて、入札メッセージを発行す
る。

【００２０】そして、入札メッセージを受けとった管制
センタは、入札メッセージに付加されていた移動体の情
報に基づいて、移動体を要求元に近いものから順に必要
数だけ選択する。そして、選択した移動体が所属する管
制センタに対して、落札メッセージを発行する（２
５）。この落札メッセージには、選択した移動体の識別
子及び要求元の位置を付加する。

【００２１】そして、落札メッセージを受けとった管制
センタは、落札メッセージに付加された識別子の移動体
に対して、要求元への移動指示を発行し（２６）、移動
指示を受けとった移動体が、割当て要求を発行した要求
元まで移動して、割当てが完了する（２７）。

【００２２】ここで、移動体要求メッセージに付加され
る移動体の数よりも、各管制センタからの入札メッセー
ジに付加された移動可能な移動体の数の方が少なかった
場合には、移動体要求メッセージを再度発行する。

【００２３】この実施の形態では、移動体の移動エリア
を複数の区域に分割し、各区域に管制センタを配置し、
区域内での割当てはその区域に所属する管制センタが行
なうため、規模が大きい場合や移動体の数が多い場合に
おいても、高速に割当てを行うことができ、区域間にお
いて移動体の数や要求発生の頻度に偏りがあっても、管
制センタ間のメッセージ交換により、移動体を移動させ
ることができるため、効率の良い割当てを行うことが可
能となる。

【００２４】実施の形態２．この実施の形態は、実施の
形態１において、要求元の所属区域内に割当て可能な移
動体がいない場合に、落札メッセージを発行された管制
センタが、落札メッセージで指定された移動体に対し
て、要求元の所属する区域までの移動指示を発行し、要
求元の所属する区域に到着してから、その区域に所属す
る管制センタから要求元への移動指示を受けるようにし
たものであり、この実施の形態の移動体割当て方法を適
用する移動体割当てシステムの構成は、図２に示すよう
に実施の形態１と同様である。

【００２５】また、管制センタ、移動体及び要求元は、
適当な通信手段を有しており、お互いにメッセージ交換
をすることができるようになっている。また、移動体は
目的地を指示すれば、その目的地に自律的に移動するこ
とができるようになっており、各管制センタは、その管
制センタの区域内に所属している移動体の位置を獲得で
きるようになっている。そして、この移動体の位置は、
各管制センタによって連続的に絶えず獲得するようにし
てもよいし、所定時間間隔で獲得するようにしてもよ
い。また、各要求元は、自己の位置を取得するなどし
て、その所属している区域を獲得できるようになってい
る。

【００２６】次に、この実施の形態の動作について説明
する。図３は、この実施の形態の動作を説明するための
説明図である。図において、図３の（ａ）は、要求元の
所属区域内に割当て可能な移動体がいる場合の動作を示
し、図３の（ｂ）は、要求元の所属区域内に割当て可能
な移動体がいない場合の動作を示している。

【００２７】まず、各移動体からは、その移動体が所属
している区域の管制センタに対して自分の位置に関する
情報や、移動可能な状態であるかなどを送信しており、
管制センタは、その所属区域に所属している移動体の状
態を把握しているものとする（３１，４１）。そして、
移動体の割当てを受けたい要求元は、要求元が所属する
区域の管制センタに対して割当て要求を発行する（３
２、４２）。

【００２８】そして、割当て要求を受けとった管制セン
タは、その所属区域内に割当て可能な移動体があれば、
その中から要求元に最近距離にある移動体に移動指示を
出し（３３）、移動指示を受けとった移動体が、指定さ
れた要求元まで移動して、割当てが完了する（３４）。

【００２９】また、割当て要求を受けとった管制センタ
の所属区域内に割当て可能な移動体がなければ、管制セ
ンタ間で、次に示すようなメッセージ交換を行ない、他
の区域から移動体を移動させて割当てを行なう。まず、
割当て要求を受けとった管制センタは、その管制センタ
が持っている宛先選択率に従って確率的に決められた管
制センタの宛先を、移動体要求メッセージの宛先として
付加し、その宛先の管制センタに対して、移動体要求メ
ッセージを発行する（４３）。

【００３０】この宛先選択率は、総和が１となるよう
な、他の管制センタの個数分の数字の組みからなるもの
である。そして、この宛先選択率の値は、あらかじめシ
ステムの設計者が、システムの形態に応じて、ヒューリ
スティックに決定するものであり、移動体割当てシステ
ムを模擬できるシミュレータがあれば、候補となるいく
つかの組み合わせで評価を行い、待ち時間の最小化な
ど、システムの目的関数をより最適化する組を採用すれ
ばよい。

【００３１】例えば、１０個の管制センタ（Ａ₀ ，
Ａ₁ ，…，Ａ₉ ）から成るシステムで、管制センタＡ₀
からは、Ａ₁ ，Ａ₂ ，…，Ａ₉ の順で距離が短いとす
る。このとき設計者が、距離の近い上位４管制センタに
等確率で移動体要求メッセージを発行する、というよう
に決めれば、宛先選択率は以下に示すようになる。 （0.25,0.25,0.25,0.25,0,0,0,0,0 ）

【００３２】そして、このような宛先選択率の場合、移
動体が１つ必要なときには、管制センタＡ₁ ，Ａ₂ ，Ａ
₃ ，Ａ₄ に対する宛先選択率は同じなので、等確率で管
制センタＡ₁ ，Ａ₂ ，Ａ₃ ，Ａ₄ の内の１つの管制セン
タが宛先として選択され、その管制センタに対して移動
体要求メッセージを発行することになる。

【００３３】また、複数の移動体が同時に必要であれ
ば、宛先選択率に従って、複数の移動体のそれぞれにつ
いて、移動体の要求先の管制センタを１つずつ決定す
る。その結果、１つの管制センタに複数の要求を発行す
ることになれば、その管制センタへの移動体要求メッセ
ージにその要求数を付加する。

【００３４】そして、その管制センタからの移動体要求
メッセージを受けとった他の管制センタは、移動体要求
メッセージを発行した管制センタに対して、入札メッセ
ージを発行する（４４）。この入札メッセージには、移
動体要求メッセージを受けとった管制センタの所属区域
内に存在する移動可能な移動体の識別子及び位置を付加
する。このとき、ある管制センタが移動体要求メッセー
ジを複数の管制センタから受けとっていた場合には、各
移動体要求メッセージに付加された要求数の比に、移動
可能な移動体を振り分けて、入札メッセージを発行す
る。

【００３５】そして、入札メッセージを受けとった管制
センタは、入札メッセージに付加されていた移動体の情
報に基づいて、移動体を要求元に近いものから順に必要
数だけ選択する。そして、選択した移動体が所属する管
制センタに対して、落札メッセージを発行する（４
５）。この落札メッセージには、選択した移動体の識別
子及び要求元の位置を付加する。

【００３６】そして、落札メッセージを受けとった管制
センタは、落札メッセージに付加された識別子の移動体
に対して、落札メッセージを発行した管制センタが所属
する区域までの移動指示を発行する（４６）。そして、
移動指示を受けとった移動体が、指定された区域まで移
動すると（４７）、そこで、その区域に属する管制セン
タに対して到着報告メッセージを発行する（４８）。こ
の到着報告メッセージは、指定された区域への到着時だ
けでなく、到着直前に発行するようにしてもよい。

【００３７】そして、到着報告メッセージを受けとった
管制センタは、その移動体に対して、割当て要求を出し
ている要求元の中で最も早く割当て要求を出した要求元
へ移動するように、移動指示を出し（４９）、移動指示
を受けとった移動体が、要求元まで移動して、割当てが
完了する（５０）。ここで、移動体要求メッセージに付
加される移動体の数よりも、入札メッセージに付加され
た移動可能な移動体の数の方が少なかった場合には、移
動体要求メッセージを再度発行する。

【００３８】この実施の形態では、移動体の移動エリア
を複数の区域に分割し、各区域に管制センタを配置し、
区域内での割当てはその区域に所属する管制センタが行
なうため、規模が大きい場合や移動体の数が多い場合に
おいても、高速に割当てを行うことができ、区域間にお
いて移動体の数や要求発生の頻度に偏りがあっても、管
制センタ間のメッセージ交換により、移動体を移動させ
ることができるため、効率の良い割当てを行うことが可
能となり、さらに、移動体の割当て先を移動開始時に決
めるのではなく、要求元が所属する区域への到着時に、
早く到着した移動体を、先に割当て要求を出した要求元
に割当てるようにしたため、待ち時間の均衡化を図るこ
とが可能となる。

【００３９】

【発明の効果】以上のように、本発明によれば、所定領
域を複数の区域に分割して、各区域ごとに管制センタを
配置し、区域内での割当てをその区域に所属する管制セ
ンタが行ない、要求元からの割当て要求に対して、その
所属する区域内に割当て可能な移動体がなければ、予め
他の管制センタのそれぞれについて設定された宛先選択
率に基づいて、移動体を要求する管制センタを決定し、
その決定した管制センタに対して、移動体要求メッセー
ジを発行し、その管制センタとの間で、入札メッセージ
及び落札メッセージのやり取りを行い、移動体の割当て
を行うようにしたので、規模が大きい場合や移動体の数
が多い場合においても、高速に割当てを実現することが
でき、区域間において移動体の数や要求発生の頻度に偏
りがあっても、管制センタ間のメッセージ交換により、
移動体を移動させることができるため、効率の良い割当
てができるという効果を有する。

【図面の簡単な説明】

【図１】実施の形態１の動作を説明するための説明図で
ある。

【図２】本発明の移動体割当て方法を説明するための説
明図である。

【図３】実施の形態２の動作を説明するための説明図で
ある。

Claims (2)

【特許請求の範囲】
1. 【請求項１】 所定領域内に複数の移動体及びその移動
   体の割当てを要求する複数の要求元を存在させ、前記移
   動体の割当てを要求した複数の要求元に対して前記複数
   の移動体を繰り返し割当てる移動体割当て方法におい
   て、 前記所定領域を複数の区域に分割して、各区域ごとに管
   制センタを配置し、 前記区域内に存在する要求元及び移動体を、その区域に
   所属する要求元及び移動体とし、 移動体の割当てを受けたい要求元では、その要求元が所
   属する区域の管制センタに対して割当て要求を発行し、 前記割当て要求を受けとった管制センタでは、その所属
   する区域内に割当て可能な移動体があれば、その移動体
   の中から割当て要求を発行した要求元に最近距離にある
   移動体を選択し、その選択した移動体に対して移動指示
   を発行して、移動体の割当てを行ない、その所属する区
   域内に割当て可能な移動体がなければ、予め他の管制セ
   ンタのそれぞれについて設定された宛先選択率に基づい
   て、移動体を要求する管制センタを決定し、その決定し
   た管制センタに対して、移動体要求メッセージを発行
   し、 その移動体要求メッセージを受けとった管制センタで
   は、その管制センタの所属する区域内の移動可能な移動
   体の位置及び識別子を付加した入札メッセージを、前記
   移動要求メッセージを発行した管制センタに対して発行
   し、 前記管制センタからの入札メッセージを受けとった管制
   センタでは、その入札メッセージに付加された移動体の
   情報に基づいて、前記割当て要求を発行した要求元に近
   い移動体を順に必要数だけ選択して、その移動体の識別
   子及び前記割当て要求を発行した要求元の位置を付加し
   た落札メッセージを、選択した移動体の所属する管制セ
   ンタに対して発行し、 その落札メッセージを受けとった管制センタでは、その
   落札メッセージに付加された識別子の移動体に対して、
   前記割当て要求を発行した要求元への移動指示を発行し
   て、移動体の割当てを行うことを特徴とする移動体割当
   て方法。
2. 【請求項２】 所定領域内に複数の移動体及びその移動
   体の割当てを要求する複数の要求元を存在させ、前記移
   動体の割当てを要求した複数の要求元に対して前記複数
   の移動体を繰り返し割当てる移動体割当て方法におい
   て、 前記所定領域を複数の区域に分割して、各区域ごとに管
   制センタを配置し、 前記区域内に存在する要求元及び移動体を、その区域に
   所属する要求元及び移動体とし、 移動体の割当てを受けたい要求元では、その要求元が所
   属する区域の管制センタに対して割当て要求を発行し、 前記割当て要求を受けとった管制センタでは、その所属
   する区域内に割当て可能な移動体があれば、その移動体
   の中から割当て要求を発行した要求元に最近距離にある
   移動体を選択し、その選択した移動体に対して移動指示
   を発行して、移動体の割当てを行ない、その所属する区
   域内に割当て可能な移動体がなければ、予め他の管制セ
   ンタのそれぞれについて設定された宛先選択率に基づい
   て、移動体を要求する管制センタを決定し、その決定し
   た管制センタに対して、移動体要求メッセージを発行
   し、 その移動体要求メッセージを受けとった管制センタで
   は、その管制センタの所属する区域内の移動可能な移動
   体の位置及び識別子を付加した入札メッセージを、前記
   移動要求メッセージを発行した管制センタに対して発行
   し、 前記管制センタからの入札メッセージを受けとった管制
   センタでは、その入札メッセージに付加された移動体の
   情報に基づいて、前記割当て要求を発行した要求元に近
   い移動体を順に必要数だけ選択して、その移動体の識別
   子及び前記割当て要求を発行した要求元の位置を付加し
   た落札メッセージを、選択した移動体の所属する管制セ
   ンタに対して発行し、 その落札メッセージを受けとった管制センタでは、その
   落札メッセージに付加された識別子の移動体に対して、
   前記割当て要求を発行した要求元が所属する区域への移
   動指示を発行し、 移動指示を受け取った移動体では、その移動指示により
   指示された区域まで移動すると、その区域に所属する管
   制センタに対して、到着報告メッセージを発行し、 その到着報告メッセージを受け取った管制センタでは、
   その到着報告メッセージを発行した移動体に対して、そ
   の管制センタが所属する区域内で最も早く割当て要求を
   発行した要求元への移動指示を発行して、移動体の割当
   てを行うことを特徴とする移動体割当て方法。