(57)【要約】【課題】  デッドロックからの総回復時間を最小とできるように改良した移動体システム及びそのデッドロック回復手法を提供することを目的とする。【解決手段】  移動体を離散時間で管理する移動体システムにおいて、移動体が相互に前方の区間を塞ぎ合うことにより閉路が存在するときにデッドロックが発生したと判定し、デッドロックが発生したと判定された場合には、例外処理として、閉路を構成する移動体のいずれかを本来の走行方向とは逆向きに走行経路上を走行させる回復動作を行うに際し、閉路からの退避路候補について４つの関係を与え、回復動作の干渉を考慮する必要がある同一のデッドロック群に属するデッドロックについては、右方最短退避路、右方次最短退避路、左方最短退避路及び左方次最短退避路から選択された退避路の組み合わせに従って前記回復動作を実行するので、デッドロックからの総回復時間を最小化することができる。【選択図】図３６
2010176607.tif 000002
【特許請求の範囲】
【請求項１】
予め方向付けされた梯子型の走行経路と、
前記走行経路上を移動する移動体と、
前記移動体の目的地までの経路を与える中央処理装置とからなり、
前記走行経路は、前記移動体が一台のみ進入可能な複数区間に分割され、
前記移動体は、前方が移動体の存在しない区間であるときのみ移動可能であり、
前記中央処理装置は、前記移動体を離散時間で管理することにより前記移動体を１単位時間当たり１区間移動させる移動体システムにおいて、
前記中央処理装置は、前記移動体が相互に前方の区間を塞ぎ合うことにより閉路が存在するときにデッドロックが発生したと判定するデッドロック検知部と、前記デッドロック検知部によりデッドロックが発生したと判定された場合には、例外処理として、前記閉路を構成する前記移動体のいずれかを本来の走行方向とは逆向きに前記走行経路上を走行させる回復動作を行うデッドロック回復部とを備えることを特徴とする移動体システム。
【請求項２】
前記デッドロック回復部は、前記閉路の中の各区間を始点として、前記移動体の存在しない任意の区間を終点とする退避路候補を探索することを特徴とする請求項１記載の移動体システム。
【請求項３】
前記デッドロック回復部は、２つの退避路候補の間に対して、“同時選択不可”、“並行動作可能”、“先行制約”又は“任意順序実行可、かつ、並行動作不可”の四つの関係を付与することを特徴とする請求項２記載の移動体システム。
【請求項４】
前記デッドロック回復部は、前記梯子型の走行経路上において隣接する複数のデッドロックについては、一方向から順に番号を付与するものとし、番号が増える方向を左方と表記し、逆に、番号が少なくなる方向を右方と表記したときに、右方のデッドロックから左方にでる左方最短退避路と、左方のデッドロックから右方にでる右方最短退避路について、２つの退避路候補が同時選択不可であるならば、総回復時間最小化のために退避路候補の組み合わせを求める必要があり、両者のデッドロックは同一のデッドロック群に属すると判定することを特徴とする請求項３記載の移動体システム。
【請求項５】
前記デッドロック回復部は、同一のデッドロック群に属する複数のデッドロックからの退避路組み合わせとして、各デッドロック間に前記移動体が存在しない区間が存在するとの条件の下で、左方のデッドロックから右方に出る右方最短退避路及び右方次最短退避路と、右方のデッドロックから左方へ出る左方最短退避路及び左方次最短退避路とからなる４通りの組み合わせから、総回復時間を最小とする退避路の組み合わせを選択することを特徴とする請求項４記載の移動体システム。
【請求項６】
前記デッドロック回復部は、前記右方最短退避路、前記右方次最短退避路、前記左方最短退避路及び前記左方次最短退避路から選択された退避路の組み合わせに従って前記回復動作を実行することを特徴とする請求項５記載の移動体システム。
【請求項７】
前記デッドロック検知部は、前記移動体の各々位置情報を得るために、前記移動体の動作を全て停止させることを特徴とする請求項１記載の移動体システム。
【請求項８】
前記デッドロック検知部は、前記移動体の全ての位置情報を集計した後、前記各移動体の現在位置から次の移動先を頂点とする辺を生成することにより区間割り当てグラフを構成することを特徴とする請求項７記載の移動体システム。
【請求項９】
前記デッドロック検知部は、区間割り当てグラフ中を探索して閉路が存在するときにはデッドロックが存在すると判定することを特徴とする請求項８記載の移動体システム。
【請求項１０】
予め方向付けされた梯子型の走行経路と、
前記走行経路上を移動する移動体と、
前記移動体の目的地までの経路を与える中央処理装置とからなり、
前記走行経路は、前記移動体が一台のみ進入可能な複数区間に分割され、
前記移動体は、前方が移動体の存在しない区間であるときのみ移動可能であり、
前記中央処理装置は、前記移動体を離散時間で管理することにより前記移動体を１単位時間当たり１区間移動させる移動体システムにおいて、
前記中央処理装置は、前記移動体が相互に前方の区間を塞ぎ合うことにより閉路が存在するときにデッドロックが発生したとデッドロック検知部により判定し、前記デッドロック検知部によりデッドロックが発生したと判定された場合には、例外処理として、前記閉路を構成する前記移動体のいずれかを本来の走行方向とは逆向きに前記走行経路上を走行させる回復動作をデッドロック回復部により行うことを特徴とする移動体システムのデッドロック回復手法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、移動体システム及びそのデッドロック回復手法に関する。詳しくは、デッドロックからの総回復時間を最小とできるように改良したものである。
【背景技術】
【０００２】
工場や倉庫、病院等で材料、部品、薬品などの運搬等に用いられる搬送ロボット、搬送台車等の自動走行移動体（以下、移動体）による無人搬送システムにおいて、特許文献１に示すような、複数の移動体がそれぞれの進行方向を閉塞されてデッドロックとなり、無人搬送システムが停止するのを防ぐためのシステム制御技術が開発されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開平６−８３４４４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
（ｉ）デッドロックが発生する毎に経路の再探索をするため、デッドロックからの回復動作のために退避先が競合して新たなデッドロックが発生する場合がある。
（ｉｉ）複数のデッドロックが同時発生した場合を想定していないため、その状態になった時、デッドロックから回復できない場合がある。
（ｉｉｉ）またデッドロックに関係する移動体が多くなれば、デッドロックから復帰するための時間が膨大にかかる場合がある。
【課題を解決するための手段】
【０００５】
上記課題を解決する本発明の請求項１に係る移動体システムは、予め方向付けされた梯子型の走行経路と、前記走行経路上を移動する移動体と、前記移動体の目的地までの経路を与える中央処理装置とからなり、前記走行経路は、前記移動体が一台のみ進入可能な複数区間に分割され、前記移動体は、前方が移動体の存在しない区間であるときのみ移動可能であり、前記中央処理装置は、前記移動体を離散時間で管理することにより前記移動体を１単位時間当たり１区間移動させる移動体システムにおいて、前記中央処理装置は、前記移動体が相互に前方の区間を塞ぎ合うことにより閉路が存在するときにデッドロックが発生したと判定するデッドロック検知部と、前記デッドロック検知部によりデッドロックが発生したと判定された場合には、例外処理として、前記閉路を構成する前記移動体のいずれかを本来の走行方向とは逆向きに前記走行経路上を走行させる回復動作を行うデッドロック回復部とを備えることを特徴とする。
【０００６】
上記課題を解決する本発明の請求項２に係る移動体システムは、請求項１において、前記デッドロック回復部は、前記閉路の中の各区間を始点として、前記移動体の存在しない任意の区間を終点とする退避路候補を探索することを特徴とする。
【０００７】
上記課題を解決する本発明の請求項３に係る移動体システムは、請求項２において、前記デッドロック回復部は、２つの退避路候補の間に対して、“同時選択不可”、“並行動作可能”、“先行制約”又は“任意順序実行可、かつ、並行動作不可”の四つの関係を付与することを特徴とする。
【０００８】
上記課題を解決する本発明の請求項４に係る移動体システムは、請求項３において、前記デッドロック回復部は、前記梯子型の走行経路上において隣接する複数のデッドロックについては、一方向から順に番号を付与するものとし、番号が増える方向を左方と表記し、逆に、番号が少なくなる方向を右方と表記したときに、右方のデッドロックから左方にでる左方最短退避路と、左方のデッドロックから右方にでる右方最短退避路について、２つの退避路候補が同時選択不可であるならば、総回復時間最小化のために退避路候補の組み合わせを求める必要があり、両者のデッドロックは同一のデッドロック群に属すると判定することを特徴とする。
【０００９】
上記課題を解決する本発明の請求項５に係る移動体システムは、請求項４において、前記デッドロック回復部は、同一のデッドロック群に属する複数のデッドロックからの退避路組み合わせとして、各デッドロック間に前記移動体が存在しない区間が存在するとの条件の下で、左方のデッドロックから右方に出る右方最短退避路及び右方次最短退避路と、右方のデッドロックから左方へ出る左方最短退避路及び左方次最短退避路とからなる４通りの組み合わせから、総回復時間を最小とする退避路の組み合わせを選択することを特徴とする。
【００１０】
上記課題を解決する本発明の請求項６に係る移動体システムは、請求項５において、前記デッドロック回復部は、前記右方最短退避路、前記右方次最短退避路、前記左方最短退避路及び前記左方次最短退避路から選択された退避路の組み合わせに従って前記回復動作を実行することを特徴とする。
【００１１】
上記課題を解決する本発明の請求項７に係る移動体システムは、請求項１において、前記移動体の各々位置情報を得るために、前記移動体の動作を全て停止させることを特徴とする。
【００１２】
上記課題を解決する本発明の請求項８に係る移動体システムは、請求項７において、前記移動体の全ての位置情報を集計した後、前記各移動体の現在位置から次の移動先を頂点とする辺を生成することにより区間割り当てグラフを構成することを特徴とする。
【００１３】
上記課題を解決する本発明の請求項９に係る移動体システムは、請求項８において、区間割り当てグラフ中を探索して閉路が存在するときにはデッドロックが存在すると判定することを特徴とする。
【００１４】
上記課題を解決する本発明の請求項１０に係る移動体システムのデッドロック回復手法は、予め方向付けされた梯子型の走行経路と、前記走行経路上を移動する移動体と、前記移動体の目的地までの経路を与える中央処理装置とからなり、前記走行経路は、前記移動体が一台のみ進入可能な複数区間に分割され、前記移動体は、前方が移動体の存在しない区間であるときのみ移動可能であり、前記中央処理装置は、前記移動体を離散時間で管理することにより前記移動体を１単位時間当たり１区間移動させる移動体システムにおいて、前記中央処理装置は、前記移動体が相互に前方の区間を塞ぎ合うことにより閉路が存在するときにデッドロックが発生したとデッドロック検知部により判定し、前記デッドロック検知部によりデッドロックが発生したと判定された場合には、例外処理として、前記閉路を構成する前記移動体のいずれかを本来の走行方向とは逆向きに前記走行経路上を走行させる回復動作をデッドロック回復部により行うことを特徴とする。
【発明の効果】
【００１５】
（Ｉ）デッドロックからの回復動作中には新たなデッドロックが発生しない。
（ＩＩ）複数のデッドロックが同時発生した場合でもデッドロックから回復できる。
（ＩＩＩ）デッドロックからの回復時間を最小化するよう最適化されている。
【図面の簡単な説明】
【００１６】
【図１】梯子型の走行経路の説明図である。
【図２】分割された有向辺の説明図である。
【図３】走行経路の移動可能性を表現するグラフの説明図である。
【図４】移動体が移動可能な走行経路の説明図である。
【図５】移動先が競合する場合の説明図である。
【図６】同一交差点上を複数移動体が同時に通過しようとする場合の説明図である。
【図７】走行経路上のデッドロックの説明図である。
【図８】本発明の一実施例に係るデッドロック回復手法のアルゴリズム（概略）である。
【図９】デッドロック検知部を示すフローチャートである。
【図１０】閉路が存在しない区間割り当てグラフである。
【図１１】閉路（単数）が存在する区間割り当てグラフである。
【図１２】閉路（複数）が存在する区間割り当てグラフである。
【図１３】デッドロック回復部を示すフローチャートである。
【図１４】最短の退避路を示す説明図である。
【図１５】退避路探索方法を示すフローチャートである。
【図１６】退避路探索を行う場合の説明図である。
【図１７】同時選択不可の説明図である。
【図１８】同時選択不可の説明図である。
【図１９】同時選択不可の説明図である。
【図２０】並行動作可能の説明図である。
【図２１】先行制約の説明図である。
【図２２】先行制約の説明図である。
【図２３】並行動作可能の説明図である。
【図２４】任意順序実行可かつ並行動作不可の説明図である。
【図２５】任意順序実行可かつ並行動作不可の説明図である。
【図２６】退避路間関係付与方法を示すフローチャートである。
【図２７】退避路間関係付与方法の具体例の説明図である。
【図２８】図２７のデッドロック退避路に退避路間関係を付与した結果を示す表である。
【図２９】異なるデッドロック群に属する２個のデッドロックの関係を示す説明図である。
【図３０】同一のデッドロック群に属する２個のデッドロックの関係を示す説明図である。
【図３１】同一のデッドロック群に属する３個のデッドロックの関係を示す説明図である。
【図３２】デッドロック群分離方法を示すフローチャートである。
【図３３】デッドロック群分離方法の具体例の説明図である。
【図３４】退避路の組み合わせを表現するために使用される多段ネットワークの説明図である。
【図３５】退避路組み合わせ方法を示すフローチャートである。
【図３６】退避路組み合わせ方法の具体例の説明図である。
【図３７】図３６のデッドロック退避路から構成した多段ネットワークの説明図である。
【発明を実施するための形態】
【００１７】
以下、本発明の移動体システム及びデッドロック回復手法の実施の実施の形態について、図面を参照して詳細に説明すると共に移動体システムの前提となる走行経路、移動体動作規則及びデッドロックについても順を追って説明する。
【００１８】
ここで、移動体システムとは、移動体を用いた構内物流システムをいう。例えば、半導体工場等で部品等の搬送や、病院内での薬品運搬等に用いられる。移動体システムでは、一般に、移動体の誘導のためにガイドパスを引く。ガイドパスが移動体の走行経路と同義である。
【００１９】
最初に、前提条件として、実施例において用いる走行経路及び移動体の動作規則の説明をする。
本実施例においては、“各デッドロック間に少なくとも１区間以上、空き区間が存在する”という条件を設定する。
上記の条件を置いた場合、移動体群のデッドロック回復動作について、最初の移動体の回復動作が開始してから、最後の移動体の回復動作が完了するまでの時間を最小化できる。
【００２０】
以下に説明する実施例中では、デッドロック検知方法、退避路探索方法及び退避路間関係付与方法、デッドロック群分離方法、退避路組み合わせ方法について詳細に述べる。
【００２１】
“各デッドロック間に空き区間が存在するという”条件を置いた場合、後述するはしご型（ラダー型）の走行経路では、後述のデッドロック群分離方法、退避路組み合わせ方法により、全てのデッドロックの回復時間を最小化できる。
【実施例１】
【００２２】
（１）走行経路説明
移動体の走行経路として、図１に示すように、左右方向に延びる梯子型の走行経路を想定する。
走行経路としては、必ずしも図１と同一の形状を取る必要はなく、後述する走行経路のグラフ表現と等価な移動可能性を持っている走行経路であればよい。
運行制御を容易にするために、走行経路は、予め方向付けされている。
走行経路は、予め移動体の制動距離以上の区間に分割されている。
【００２３】
図２のように、上下の有向辺をｋ区間ずつ（ｋは１以上の整数）、はしごを構成する双方向辺上を１区間として分割する。有向辺とは、矢印で示すように、一方向にのみ方向付けされている走行経路であり、双方向辺とは、矢印で示すように、双方向に方向付けされている走行経路である。
全ての区間には固有の区間番号が割り当てられている。
【００２４】
中央処理装置（図示省略）により区間の番号、座標が管理されている。
衝突防止制御のため、どの区間も同時に高々一台の移動体が進入可能とする。
ホームステーションと呼ばれる特別な区間が存在する。
【００２５】
図３のように、区間番号ｉの指す区間を頂点ｉ、ある区間ｉから他の区間ｊへ移動可能である場合に辺ｅi,jを引くことで走行経路の移動可能性を表現するグラフを構成する。
ここで、ｉとは任意の区間番号を指し、例えば、図３において区間番号１の指す区間は頂点１を表す。
以下では、移動体の移動については、上記グラフを用いて説明する。
【００２６】
（２）移動体動作規則説明
移動体の動作規則について以下に述べる。
移動体はそれぞれ固有の移動体番号を持つ。
移動体が搬送タスクを割当てられているとき、移動体の目的地までの経路は中央処理装置により与えられ、その経路に従って搬送を行う。
中央処理装置から命令がある場合のみ、経路を変更可能である。
搬送タスクを持たない全ての移動体はホームステーションを目的地とする。
【００２７】
図４のように、移動先が移動体の存在しない区間（空き区間）であるときのみ、移動体は移動可能とする。
移動体システムは時間の流れを離散的に表現した、離散時間で管理される。
どの移動体も、１単位時間に１区間移動可能である。
図５のように、複数の移動体の移動先が競合する場合は、優先度最高の移動体に対して移動許可を与える。
優先度は予め定めた条件に基づき、中央処理装置が決定する。
【００２８】
図６のように同一交差点上を複数移動体が同時に通過しようとする場合は、上記と同様に中央処理装置によって優先度を定め、優先度最高の移動体のみが交差点を通過可能とする。
移動体に与えられる搬送タスクに関しては、本発明と関連が無いため、搬送タスクの発生時刻や目的地の限定は特に考えない。
上記前提条件に基づき、移動体システムが運用されているものとする。
【００２９】
搬送先の偏りや、障害物感知による不意の停止により、移動体システムの運行に乱れが生じることがある。
これにより、走行経路内の特定箇所に移動体が密集する。
結果として、後述するデッドロックが発生して搬送が行われなくなり、移動体システムの停止を引き起こす。
【００３０】
（３）デッドロックの説明
前方が空き区間の移動体のみ移動できるという規則より、図７のように、走行経路内の閉路上に複数の移動体が空き区間を挟まず直列し、かつ、それらの移動体の進行方向が閉路の有向辺と一致すると、その閉路上の移動体は全て移動できなくなる。
このとき、移動体の進行方向を変更するなど、何らかの介入を外部から加えない限り、この閉路上に存在する移動体は永久に移動できない。
このような永久停止状態をデッドロックと呼ぶ。
【００３１】
移動体ｅ，ｆのように前方移動体を辿っていくと、最終的に閉路に到達する移動体も同様にデッドロック状態である。
移動体システムの正常運行のためには、デッドロックが存在するかどうかを検知して、もし存在するならばデッドロックから回復する操作が必要である。
デッドロックの定義より、デッドロック回復のためには進行方向の閉路を除去する必要がある。
これは、進行方向が閉路を構成している移動体の少なくとも１台の進行方向を、現在の進行方向とは別の方向に変更するか、現在存在する区間から移動させることにより実現できる。
【００３２】
このとき、デッドロックを回復する操作は、移動体システムを一旦停止して、通常の移動体システムの運行とは異なる、例外処理として実行される。
したがって、デッドロックを回復する操作中は、移動体は必ずしも、前述した「（１）走行経路説明」で設定した方向付けに従って移動する必要はないとする。
進行方向の閉路の除去によってのみデッドロック回復が可能である。
図７において、移動体ｅ，ｆの進行方向や存在位置をどのように変更したとしても、閉路ａ，ｂ，ｃ，ｄの除去は不可能である。
【００３３】
（４）アルゴリズム全体の説明
本発明の一実施例に係るデッドロック回復手法を図８に示す。図８は、デッドロック回復手法のアルゴリズムの概略を示すものであり、図中に示すように、デッドロック検知部１０及びデッドロック回復部２０とから成る。
【００３４】
（５）デッドロック検知方法の説明
デッドロック検知部１０は、図９に示すように、後述する区間割り当てグラフの生成及び区間割り当てグラフ中に閉路が存在するかどうかを判定することによりデッドロック検知方法を実施する。
もし、区間割り当てグラフ中に閉路が存在するならデッドロックが存在すると判定する。
【００３５】
（５．１）全体移動停止
まず、各移動体の現在位置を正確に得るため、また、デッドロックが存在する場合はデッドロック回復を実行するために、全移動体の動作を停止させる。
【００３６】
（５．２）区間割り当てグラフ生成
次に、全ての移動体の現在位置及び進行方向を把握するために、中央処理装置は全ての移動体に対して現在位置と、次の移動先区間を中央処理装置に送信するよう要請する。
各移動体は、中央処理装置の要請に従い、現在位置と次の移動先区間を中央処理装置に送信する。
中央処理装置は、全ての移動体の位置情報を集計した後、各移動体ｉの現在位置Ｃi，次の移動先Ｎiを頂点とし、辺ｅ′Ci,Niを生成してグラフを構成する。このとき構成したグラフを区間割当てグラフと定義する。
【００３７】
（５．３）区間割り当てグラフに閉路が存在するか否かの判定
具体例として、デッドロック検知を実行した結果、デッドロックが存在しないと判定される例を示す。
図１０のような配置において、移動体ａ，ｂ，ｃ，ｄが存在する区間をｖａ，ｖｂ，ｖｃ，ｖｄと表記すると、移動体ａからｖａ，ｖｔ，ｅ′va,vt、移動体ｂからｖｂ，ｖｃ，ｅ′vb,vc、移動体ｃからｖｃ，ｖｄ，ｅ′vc,vd、移動体ｄからｖｄ，ｖａ，ｅ′vd,vaが各々生成される。
頂点｛ｖａ，ｖｂ，ｖｃ，ｖｄ，ｖｔ｝、辺｛ｅ′va,vt，ｅ′vb,vc，ｅ′vc,vd，ｅ′vd,va｝から成るグラフ中を探索することで閉路が存在しないことが確認できる。
この場合、デッドロックが存在しないと判定して、終了する。
【００３８】
一方、他の具体例として、デッドロック検知を実行した結果、デッドロックが存在すると判定される例を示す。
図１１の場合に、移動体ａ，ｂ，ｃ，ｄ，ｅが存在する区間をｖａ，ｖｂ，ｖｃ，ｖｄ，ｖｅと表記し、同様に区間割り当てグラフを構成すると、移動体ａからｖａ，ｖｂ，ｅ′va,vb，移動体ｂからｖｂ，ｖｃ，ｅ′vb,vc、移動体ｃからｖｃ，ｖｄ，ｅ′vc,vd、移動体ｄからｖｄ，ｖａ，ｅ′vd,va、移動体ｅからｖｅ，ｖａ，ｅ′ve,vaが各々生成される。
頂点｛ｖａ，ｖｂ，ｖｃ，ｖｄ，ｖｅ｝、辺｛ｅ′va,vb，ｅ′vb,vc，ｅ′vc,vd，ｅ′vd,va，ｅ′ve,va｝から成るグラフ中を探索すると、頂点｛ｖａ，ｖｂ，ｖｃ，ｖｄ｝により閉路が構成されていることがわかる。
以下では、区間割当グラフに存在するｉ番目の閉路をＤiと表記する。
上記の場合、Ｄ1＝（ｖａ，ｖｂ，ｖｃ，ｖｄ，ｖａ）となる。
これにより、システム中にデッドロックが存在することがわかる。
【００３９】
図１２のように、閉路が複数存在する場合も、同様に判定できる。
同様に区間割当てグラフを構成し、閉路を探索する。
結果として、２つの閉路Ｄ1＝（ｖａ，ｖｂ，ｖｃ，ｖｄ，ｖａ）とＤ2＝（ｖｅ，ｖｆ，ｖｇ，ｖｈ，ｖｅ）が存在し、２箇所でデッドロックが発生していると判定される。
デッドロックの存在が確認された場合、デッドロック回復部２０を起動して、移動体システム内からデッドロックを除去する。
【００４０】
（６）デッドロック回復方法の説明
デッドロック回復部２０は、図１３に示すように、退避路探索方法、退避路間関係付与方法、デッドロック群分離方法、退避路組み合わせ方法及び移動体回復動作部とからなるデッドロック回復方法を実施する。
デッドロック回復方法とは、デッドロックを回復するために、閉路を構成する移動体から１台を選び、隣接する他の区間へ移動させることにより、閉路を除去する方法である。
【００４１】
本実施例では、特に、回復動作を原因としたデッドロックの発生を防ぐために、回復動作は、本来の走行経路の方向付けと逆向きとなるよう移動する、逆方向移動のみを用いる。
デッドロック回復動作を、後述の退避路上に存在する各移動体を１区間ずつ、退避路の向きに沿って移動させ、移動前に存在していた区間を次の移動先とし、以降は移動前の経路に復帰する動作と定義し、デッドロック回復動作により閉路の除去を行う。
【００４２】
退避路とは、図１４のように、閉路上のある移動体が存在する頂点ｖsを始点、走行経路中の任意の空き区間をｖtとして、ｖsから有向辺逆向き探索でｖtへ到達可能な有向辺逆向き最短路であるとする。
退避路は、ｖsからｖtまでの間に存在する頂点の列（ｖs，ｉ，ｊ，…，ｎ，ｖt）で表現される。
ある退避路上での回復時間は、その退避路上の各移動体が丁度１区間ずつ移動するのに要する時間の総和とする。
【００４３】
（６．１）退避路探索方法
デッドロックを回復するためには、上述の退避路を求める必要がある。
回復に用いる退避路は、後述の退避路組み合わせ方法により決定されるため、退避路探索方法により求まる退避路は、この時点では全て退避路候補である。
【００４４】
退避路探索方法は、図１５に示すフローチャートに従い、退避路候補を求める。
まず、退避路候補がまだ求まっていない閉路を１つ選択する。
次に、その閉路の中から頂点を１つ選択する。
上記で選択した頂点から、有向辺逆向きに空き区間を探索する。例えば、周知の技術である幅優先探索または深さ優先探索を行い、空き区間を探索する。
【００４５】
もし、探索した区間が、探索始点の頂点を含む閉路上の頂点ならば、その方向への探索を打ち切る。
また、探索した区間が、始点からの探索において既に探索した区間である場合も、その方向への探索を打ち切る。
【００４６】
探索した区間が空き区間である場合、始点から探索した空き区間までの退避路候補を生成する。
生成した退避路候補は、検出した空き区間番号をｄ、探索の始点区間番号をｏとして、ｒd,oと表記する。
【００４７】
また、他の閉路を構成する頂点を探索した場合も同様に、検出した他閉路区間番号をｄ、探索の始点区間番号をｏとして、退避路候補ｒd,oを生成する。
生成した退避路候補が、発生したデッドロック数個の空き区間を含む場合は、その方向への探索を打ち切る。
１つ目の空き区間を見つけた時点で探索を停止しない理由は、退避先区間が競合して回復できないデッドロックが発生することを防ぐためである。
【００４８】
全ての方向に対して探索が停止したら、同閉路中のまだ探索の始点となっていない頂点を選び、同様に空き区間を探索する。
同閉路中の全ての頂点から探索を行った後、その閉路の頂点を始点とした探索により生成された退避路候補から成る退避路候補集合を生成する。
【００４９】
まだ退避路候補を生成していない閉路が存在するならば、そのような閉路を一つ選び、同様に退避路候補を生成する。
全ての閉路において退避路候補が求まった後、退避路探索方法を終了して退避路間関係付与方法に移行する。
【００５０】
具体例として、図１６を参照して、頂点ａから有向辺逆向きに探索を行う場合について説明する。
まず１区間目の探索で同閉路の頂点ｆが検出され探索を打ち切る。
次に頂点ｇから有向辺逆向きに探索を行う。
探索において２方向に分岐する場合、必ず有向辺上の区間を先に探索する。
探索の結果として、退避路候補｛ｒh,g，ｒb,g，ｒo,g，ｒi,g，ｒj,g，ｒc,g，ｒp,g，ｒd,g，ｒk,g｝を生成する。
同様に頂点ｌからの探索では、退避路候補｛ｒh,l，ｒb,l，ｒo,l，ｒi,l，ｒc,l，ｒp,l，ｒj,l，ｒd,l，ｒk,l｝を生成する。
【００５１】
頂点ｆからの探索は、１区間目の探索区間が同閉路上の頂点ａなので探索を打ち切る。
次に、頂点ｉからの探索では、｛ｒc,i，ｒb,i，ｒh,i｝を生成する。
引き続き、頂点ｄからの探索では、｛ｒc,d，ｒb,d，ｒh,d｝を生成し、頂点ｊからの探索では、｛ｒp,j，ｒk,j｝を生成し、頂点ｏからの探索では、｛ｒp,o，ｒk,o｝を生成する。
求まった退避路候補上の各々で独立に回復動作を行う場合、退避先区間が競合して回復できないデッドロックが発生する場合がある（後述する、同時選択不可な場合である）。
【００５２】
そこで、複数の退避路候補間において、各々の退避路候補上での回復動作が干渉するかどうかを求める手がかりとして、退避路候補間に存在する４つの関係、“同時選択不可”、“並行動作可能”、“先行制約”、“任意順序実行可、かつ、並行動作不可”を定義し、それについて述べる。
まず、異なる２つのデッドロックＤi，Ｄjからの退避路候補ｒix,x′，ｒjy,y′（ｉ，ｊはデッドロック番号を表し、ｘ，ｘ′，ｙ，ｙ′は区間を表す頂点）において、退避先が競合するかどうか、すなわちｘとｙが同一区間であるかどうかを調べる。
退避路候補は頂点番号の列で表現されることから、文字列マッチング等周知の技術を用いて容易に調べることができる。
【００５３】
（６．１．１）“同時選択不可”
図１７に示すように、ｘとｙが同一区間である場合、デッドロック回復に用いる退避路の組み合わせに同時に含んではならないとして、同時選択不可ｒix,x′ＸＯＲｒjy,y′という関係を与える（記号ＸＯＲは排他的論理和と同義であり、左項または右項の退避路候補の一方のみ選択可能であることを意味する）。
【００５４】
図１８に示すように、ｘが他の閉路上の頂点であり、かつ、その頂点とｙ′が異なる頂点である場合、この２つの組み合わせにおいて退避路候補ｒix,x′上で回復動作を行うのは不可能であるため、デッドロック回復に用いる退避路の組み合わせに同時に含んではならないとして、同時選択不可ｒix,x′ＸＯＲｒjy,y′という関係を与える。
【００５５】
また、図１９に示すように、ｘがｙ′と等しく、かつｘ′がｙと等しい場合、ｘ，ｙ共に空き区間になる見込みが無く、両方の退避路候補上で動作不可能である。
そのため、これらの退避路候補はデッドロック回復に用いる退避路の組み合わせに同時に含んではならないという同時選択不可ｒix,x′ＸＯＲｒjy,y′という関係を与える。
【００５６】
（６．１．２）“並行動作可能”
また、図２０に示すように、ｒix,x′，ｒjy,y′がお互いに共通区間を全く含まない場合、互いの退避路上での回復動作は干渉しないため、並行動作可能ｒix,x′‖ｒjy,y′という関係を与える（記号‖は、左項の退避路候補上での回復動作と右項の退避路候補上での回復動作を並行的に実行できることを意味する）。
【００５７】
（６．１．３）“先行制約”
次に、図２１のように、あるデッドロックＤiからの退避路候補ｒix,x′の終点が、他のデッドロックＤjからの退避路候補ｒjy,y′の始点である場合、すなわちｘとｙ′が同一区間である場合、Ｄjの回復動作が完了した後に、区間ｘが空き区間となるため、ｒix,x′上で回復動作を実行できる。
【００５８】
このように、退避路候補ｒix,x′の終点が空き区間ではないが、他の退避路候補ｒjy,y′での回復動作後であればデッドロック回復に用いることができる場合、回復動作に順序付けを行うことによりｒix,x′をデッドロック回復に用いることができる。
このとき、ｒjy,y′上での回復動作をｒix,x′に先行させなければならないとして、先行制約ｒjy,y′＜ｒix,x′という関係を与える（記号＜は、左項の退避路候補上での回復動作が右項の退避路候補上での回復動作に対して先行しなければならないことを意味する）。
【００５９】
同様に、記号＞は右項の退避路候補上での回復動作が左項の退避路候補上での回復動作に対して先行しなければならないことを意味する。
また、図２２のように、ある退避路候補ｒjy,y′の終点区間が、退避路ｒix,x′中に含まれる場合、ｒix,x′上での回復動作を先行させると区間ｙが空き区間ではなくなり、ｒjy,y′上で回復動作が実行できなくなる。
そのため、ｒjy,y′上での回復動作をｒix,x′上での回復動作に先行させる必要があるため、先行制約ｒjy,y′＜ｒix,x′という関係が与えられる。
【００６０】
（６．１．４）“並行動作可能”
また、図２３に示すように、ｘ，ｙが空き区間であり、かつ、ｒix,x′がｙを含み、かつ、ｒjy,y′がｘを含む場合を考える。
このとき、ｒix,x′中のｙからｘ間の移動体と、ｒjy,y′中のｘからｙ間の移動体はそれぞれ並行動作可能、かつ、これらの区間の上にいる移動体を先に動かさなければ片方の退避路候補上での動作が実行不可能となる。
【００６１】
ただし、これらの２つの動作のうち少なくとも一方が完了すると、以降の動作は関係“‖”か“＜”が付与された場合と等価になる。
このときの総回復時間は並行動作可能な場合と同一であるため、便宜上、並行動作可能であるとして扱い、関係ｒix,x′‖ｒjy,y′を付与する。
【００６２】
（６．１．５）“任意順序実行可かつ並行動作不可”
最後に、２つの異なるデッドロックＤi，Ｄjからの退避路候補ｒix,x′，ｒjy,y′に関して、図２４のようにお互いの退避路候補の始点、終点いずれもお互いの退避路候補に含まれない場合、どちらの退避路候補上での回復動作を実行を先に実行してもよい。
ただし、共有している区間上では同時に回復動作を実行することはできないため、任意順序実行可かつ並行動作不可ｒix,x′＜＞ｒjy,y′という関係を与える（記号＜＞は、左項及び右項の退避路候補のどちらの退避路上での回復動作を先行して実行してもよいが、並行的には実行できないことを意味し、プログラミング言語Ｐａｓｃａｌ等で用いられるノットイコールを表す演算子とは異なるものとする。）。
【００６３】
他の任意順序実行可かつ並行動作不可の場合は、図２５に示すように、ｒix,x′がｙ′を含み、かつ、ｙがｒix,x′に含まれない場合が存在する。
この場合、ｒix,x′とｒjy,y′は互いに異なる終点を持ち、かつ、各退避路候補中にもう一方の退避路候補の終点が存在しないため、一方で回復動作を実行するともう片方の上で回復動作が実行不可となることは無い。
ただし、始点を含めたいくつかの頂点を共通して持ち、並行動作できない箇所が存在するため、関係ｒix,x′＜＞ｒjy,y′を付与する必要がある。
【００６４】
（６．２）退避路間関係付与方法
退避路間関係付与方法は、退避路候補間の関係を自動的に付与するための方法であり、図２６に示すフローチャートに従って行われる。
まず、ある退避路候補ｒix,x′の終点区間ｘが他の閉路の頂点であるが、その閉路からはｘを始点とした退避路候補が生成されていない場合、どのような退避路候補の組み合わせにおいてもｒix,x′上での回復動作は実行不可能である。
そのような、区間ｘを終点とした退避路候補を、全ての退避路候補集合から除去する。
【００６５】
次に、２つのデッドロックＤi，Ｄjから、関係が付与されていない退避路候補を１つずつ選択し、ｒix,x′，ｒjy,y′とする。
２つの退避路候補ｒix,x′，ｒjy,y′ついて、区間ｘと区間ｙが同一区間である場合、同時選択不可ｒix,x′ＸＯＲｒjy,y′という関係を付与して、まだ関係が付与されていない２つの退避路候補を新たに選択し直す。
２つの退避路候補ｒix,x′，ｒjy,y′について、区間ｘがＤj上の区間であり、かつ、区間ｘと区間ｙ′が異なる区間である場合、同時選択不可ｒix,x′ＸＯＲｒjy,y′という関係を付与して、まだ関係が付与されていない２つの退避路候補を新たに選択し直す。
【００６６】
２つの退避路候補ｒix,x′，ｒjy,y′について、区間ｘが区間ｙ′と等しく、かつ、区間ｙが区間ｘ′と等しい場合、同時選択不可ｒix,x′ＸＯＲｒjy,yという関係を付与して、まだ関係が付与されていない２つの退避路候補を新たに選択し直す。
２つの退避路候補ｒix,x′，ｒjy,y′について、共通して保持する区間が存在しなければ、並行動作可能ｒix,x′‖ｒjy,yという関係を付与して、新たにまだ関係が付与されてない２つの退避路候補を選択し直す。
【００６７】
２つの退避路候補ｒix,x′，ｒjy,y′について、区間ｘ，ｙが空き区間であり、かつ、区間ｘが退避路候補ｒix,x′に含まれ、かつ、区間ｙが退避路候補ｒix,x′に含まれる場合、並行動作可能ｒix,x′‖ｒjy,yという関係を付与して、新たにまだ関係が付与されてない２つの退避路候補を選択し直す。
２つの退避路候補ｒix,x′，ｒjy,y′について、区間ｘと区間ｙ′が同一区間である場合、先行制約ｒjy,y′＜ｒix,x′という関係を付与して、まだ関係が付与されていない２つの退避路候補を新たに選択し直す。
【００６８】
上記の逆も同時に調べる。すなわち、２つの退避路候補ｒix,x′，ｒjy,y′について、区間ｙと区間ｘ′が同一区間である場合、先行制約ｒix,x′＜ｒjy,y′という関係を付与して、まだ関係が付与されていない２つの退避路候補を新たに選択し直す。
２つの退避路候補ｒix,x′，ｒjy,y′について、区間ｘが退避路候補ｒjy,y′に含まれる場合、先行制約ｒix,x′＜ｒjy,y′という関係を付与して、まだ関係が付与されていない２つの退避路候補を新たに選択し直す。
上記の逆も同時に調べる。２つの退避路候補ｒix,x′，ｒjy,y′について、区間ｙが退避路候補ｒix,x′に含まれる場合、先行制約ｒjy,y′＜ｒix,x′という関係を付与して、まだ関係が付与されていない２つの退避路候補を新たに選択し直す。
【００６９】
上記のいずれの関係も付与されない場合、任意順序実行可、かつ、並行動作不可ｒjy,y′＜＞ｒix,x′という関係を付与して、まだ関係が付与されていない２つの退避路候補を新たに選択し直す。
全ての退避路候補ｒix,x′，ｒjy,y′間に関係が付与されたら、退避路間関係付与方法は終了となる。
【００７０】
図２７においては、区間ｇを始点とした退避路候補と、頂点ｄ，ｉ，ｊ，ｏからの退避路候補間に図２８に示すような関係が付与される。
図２８に示す行列において、行要素が関係の左項、列要素が関係の右項となる。
ｒ＞ｒ′は、先行制約を逆に書いたもので、ｒ′上での回復動作がｒ上での回復動作に先行しなければならないことを表す。
他の頂点からの退避路候補についても同様に関係が付与される。
【００７１】
（６．３）デッドロック群分離方法
上記のように退避路間関係を付与した後、回復動作の干渉を考慮するべきデッドロックの集合として、デッドロック群を定義する。
左右方向に延びるはしご型走行経路の特徴として、各デッドロックから生成される退避路候補について、そのデッドロックの右方へ出る退避路候補集合と、左方へ出る退避路候補集合の２通りに分類できる。
【００７２】
また、区間の位置情報を中央処理装置が管理していることから、複数のデッドロックが発生した時にデッドロックの位置関係を特定することが可能であり、右端デッドロックから順番にＤ1，Ｄ2，…，Ｄmと番号付けることができる。
ｍは、発生したデッドロックの個数と等しい。
【００７３】
ここで、Ｄiから左方に出る退避路候補のうちで、双方向辺上に存在する区間を始点とし、かつ、最小区間数（等しい区間数の退避路候補が複数存在する場合は、その中から任意に１つ選択）、かつ、空き区間を終点とする退避路候補のことを左方最短退避路ｒLiと表記し（ｒは退避路候補、Ｌは左方に退避路が出ること、ｉはデッドロック番号を意味）、Ｄiから右方に出る退避路候補のうちで、双方向辺上に存在する区間を始点とし、かつ、最小区間数（等しい区間数の退避路候補が複数存在する場合は、その中から任意に１つ選択）、かつ、空き区間を終点とする退避路候補のことを右方最短退避路ｒRiと表記し（Ｒは右方に退避路が出ることを意味）、各々を定義する。
【００７４】
このとき、図２９に示すように、２つのデッドロック間に他のデッドロックを挟まないように隣接するデッドロックＤi，Ｄi+1において、Ｄiの左方最短退避路ｒLiと、Ｄi+1の右方最短退避路ｒRi+1について、２つの退避路候補が並行動作可能ｒLi‖ｒRi+1であるならば、両者のデッドロックは異なるデッドロック群に属し、回復動作の干渉を考慮する必要が無くなる。
なぜなら、Ｄiから左方、Ｄi+1から右方に出る退避路候補の中で、干渉するような退避路候補を選択することは、ｒLi，ｒRi+1のいずれか一方より回復に時間がかかる退避路候補を選ぶことになり、全体の回復時間を大きくするよう退避路候補を選ぶことになるからである。
【００７５】
逆に、図３０に示すように、２つのデッドロック間に他のデッドロックを挟まないように隣接するデッドロックＤi，Ｄi+1において、Ｄiの左方最短退避路ｒLiと、Ｄi+1の右方最短退避路ｒRi+1について、２つの退避路候補が同時選択不可ｒLiＸＯＲｒRi+1であるならば、総回復時間最小化のために退避路候補の組み合わせを求める必要があり、両者のデッドロックは同一のデッドロック群に属するとする。
また、図３１のように、連続する３つのデッドロックＤi-1，Ｄi，Ｄi+1に関して、Ｄi-1の左方最短退避路ｒLi-1と、Ｄiの右方最短退避路ｒRiがｒLi-1ＸＯＲｒRiという関係を持ち、かつ、Ｄiの左方最短退避路ｒLiと、Ｄi+1の右方最短退避路ｒRi+1がｒLiＸＯＲｒRi+1という関係を持つならば、両端のデッドロックＤi-1とＤi+1は総回復時間最小化のために退避路候補の組み合わせを求める必要があり、同一のデッドロック群に属するとする。
連続するデッドロック数が４つ以上の場合でも同様にデッドロック群を決めることができる。
【００７６】
以上のことを踏まえ、図３２に示すフローチャートに従い、デッドロック群分離方法を実施する。
総デッドロック数ｍが、ｍ＝１ならば、デッドロックＤ1をデッドロック群ＤＧ1として終了する。
まず、デッドロック番号を表す変数としてｉ＝１、デッドロック群番号を表す変数としてｋ＝１を初期値とする。
総デッドロック数ｍが、ｍ＞１ならば、デッドロックＤiをデッドロック群ＤＧkとする。
【００７７】
次に、デッドロックＤiに隣接する左方のデッドロックＤi+1について考える。
デッドロックＤi，Ｄi+1において、Ｄiの左方最短退避路ｒLiと、Ｄi+1の右方最短退避路ｒRi+1について、ｒLiＸＯＲｒRi+1であるかどうかを調べる、
もし、ｒLiＸＯＲｒRi+1でないならば、デッドロック群番号ｋ：＝ｋ＋１として、デッドロックＤi+1をデッドロック群ＤＧkとして、デッドロック番号を表す変数ｉ：＝ｉ＋１として、デッドロックＤiに隣接するデッドロックとの間に干渉が存在するかを調べる。
【００７８】
もし、ｒLiＸＯＲｒRi+1ならば、デッドロックＤi+1をデッドロック群ＤＧkとして、デッドロック番号を表す変数ｉ：＝ｉ＋１として、デッドロックＤiに隣接するデッドロックとの間に干渉が存在するかを調べる。
もし、デッドロックＤiに隣接する左方のデッドロックＤi+1について、ｉ＋１＝ｍであるならば、デッドロック群の生成ステップを終了する。
具体例として、図３３に示す例では、まず右端デッドロックＤ1と、隣接する左方デッドロックＤ2の間で、Ｄ1の左方最短退避路と、Ｄ2の右方最短退避路とが同時選択不可であるため、両者をデッドロック群ＤＧ1に属するとする。
【００７９】
同様に、デッドロックＤ2と、隣接する左方デッドロックＤ3についても同様に判定され、デッドロックＤ3をデッドロック群ＤＧ1に属するとする。
最後に、デッドロックＤ4については、Ｄ3との間に同時選択不可となる最短退避路を持たないため、新たにデッドロック群ＤＧ2を生成して、ＤＧ2に属するとする。
【００８０】
（６．４）退避路組み合わせ方法
デッドロック群の定義より、あるデッドロック群ＤＧiの中での総回復時間最小化を達成する退避路候補の組み合わせと、ＤＧjの中での総回復時間最小化を達成する退避路候補の組み合わせについて、ＤＧiの回復動作とＤＧjの回復動作はお互いに干渉しない、
したがって、各デッドロック群毎に独立に退避路候補の組み合わせを求めることができる。
既に、退避路候補が出る方向を左右で二分できることを述べた。
【００８１】
すると、あるデッドロックから選択するべき退避路候補について、１．右方最短退避路、２．後述する右方次最短退避路、３．左方最短退避路、４．後述する左方次最短退避路の４通りを考えればよい。
あるデッドロックＤiの右方次最短退避路とは、Ｄiから出る退避路候補集合において、右方へ出る退避路候補のうち、Ｄi-1の左方最短退避路が回復に用いられると仮定したときの、Ｄiの右方最短退避路と異なる終点を持つ退避路候補の中で回復時間最小の退避路候補のことである。
【００８２】
同様に、あるデッドロックＤiの左方次最短退避路とは、Ｄiから出る退避路候補集合において、左方へ出る退避路候補のうち、Ｄi+1の右方最短退避路が回復に用いられると仮定したときの、Ｄiの左方最短退避路と異なる終点を持つ退避路候補の中で回復時間最小の退避路候補のことである。
あるデッドロックＤiの右方次最短退避路ｒR′iは、Ｄi-1の左方最短退避路ｒLi-1を固定したとき、ｒLi-1＜ｒR′iか、ｒLi-1‖ｒR′iのどちらかの関係を持つ退避路候補の中で、最も小さい回復時間となる退避路候補ｒR′iとして得ることができる。
ｒLi-1＜ｒR′iとして退避路候補ｒR′iが選択される場合、ｒR′iの終点と、退避路候補ｒLi-1の始点が一致する場合は、ｒR′iの回復時間は、｛（ｒLi-1上の全移動体が１区間ずつ移動する時間）＋（ｒR′i上の全移動体が１区間ずつ移動する時間）｝とする。
【００８３】
ｒLi-1＜ｒR′iとして退避路候補ｒR′iが選択され、かつ、ｒR′iの終点が空き区間である場合は、ｒR′iの回復時間は、（ｒR′i上の全移動体が１区間ずつ移動する時間＋１）とする。
ｒLi-1‖ｒR′iとして退避路候補ｒR′iが選択された場合、ｒR′iの回復時間は、（ｒR′i上で上で各移動体が１区間ずつ移動する時間）とする。
あるデッドロックＤiの左方次最短退避路ｒL′iも同様に、Ｄi+1の右方最短退避路ｒRi+1を固定したとき、ｒRi+1＜ｒL′iか、ｒRi+1‖ｒL′iのどちらかの関係を持つ退避路候補の中で、回復時間最小となる退避路候補ｒL′iとして得ることができる。
【００８４】
左方次最短退避路の回復時間は、右方次最短退避路と同様の手順で求めることができる。
すなわち、ｒRi+1＜ｒL′iとして退避路候補ｒL′iが選択される場合、ｒL′iの終点と、退避路候補ｒRi+1の始点が一致する場合は、ｒL′iの回復時間は、｛（ｒRi+1上の全移動体が１区間ずつ移動する時間）＋（ｒL′i上の全移動体が１区間ずつ移動する時間）｝とする。
ｒRi+1＜ｒL′iとして退避路候補ｒL′iが選択され、かつ、ｒL′iの終点が空き区間である場合は、ｒL′iの回復時間は、（ｒL′i上の全移動体が１区間ずつ移動する時間＋１）とする。
【００８５】
ｒRi+1‖ｒL′iとして退避路候補ｒL′iが選択された場合、ｒL′iの回復時間は、（ｒL′i上の全移動体が１区間ずつ移動する時間）とする。
例外として、あるデッドロック群の中で、右方に隣接デッドロックが存在しないデッドロックＤ1に関しては、右方次最短退避路は存在しない。
同様に、あるデッドロック群の中で、左方に隣接デッドロックが存在しないデッドロックＤmに関しては、左方次最短退避路は存在しない。
【００８６】
退避路の組み合わせを表現するために図３４のような多段ネットワークを構成する。
任意のｓ−ｔ経路は、例えば、（ｓ，ｒR1，ｒL2，ｒR′3，ｔ）であればデッドロックＤ1からは右方最短退避路を、デッドロックＤ2からは左方最短退避路を、デッドロックＤ3からは右方次最短退避路を選んだことを意味する、のように各デッドロックから選択した退避路の組み合わせを意味する。
ｒR1，ｒL1，ｒL′1から成る段を１段目、ｒR2，ｒR′2，ｒL2，ｒL′2から成る段を２段、ｒR3，ｒR′3，ｒL3のように、ネットワーク上において、デッドロックＤiを回復させるための退避路候補が存在する段をｉ段目とする。
【００８７】
あるｉ，ｉ＋１段の間を結ぶ辺において、ｒRiから出る辺について考える。
デッドロックＤi+2の存在を考えなければ、ｉ＋１段において、４つの退避路候補はいずれもｒRiと干渉しない。
なぜなら、Ｄi+1から右方へ出る退避路候補はＤiとＤi+1との間にある空き区間を終点とするからである。
この場合、ｒRi+1が干渉を起こさないことを考えると、ｒRi+1以上に回復時間を要するｒR′i+1を選択の候補として考えなくてよいことは明らかである。
【００８８】
残りの３つの退避路候補に関しては、ｉ段で選択した退避路候補だけでは回復時間の最適性に関して言及できないため、どれも選択可能とする。
したがって、ｒRiからはｒRi+1，ｒLi+1，ｒL′i+1の３つへ辺を引く。
ｒR′iからｉ＋１段へ引く辺を考える。
ｒRiと同様に、ｒRi+1，ｒLi+1，ｒL′i+1の３つへ辺を引けばよい。
ｒLiからｉ＋１段へ引く辺を考える。
この場合、ｒRi+1が同時選択不可な関係を持つため、残りの３つ、すなわち、ｒR′i+1，ｒLi+1，ｒL′i+1へ辺を引けばよい。
【００８９】
最後に、ｒL′iから引く辺であるが、この場合はｉ＋１段へはｒRi+1のみへ辺を引けばよい。
ｒL′iとｒLi+1及びｒL′i+1は干渉しない。そのため、ｒLiを通過してそれらの退避路候補を選択する場合より、確実に回復時間が大きくなる。
ｒL′iとｒR′i+1に関しては、同時選択不可な関係を持つか、ｒRi+1を選択した場合よりも確実に回復時間が大きくなる。
以上の理由から、ｒL′iからはｒRi+1のみへ辺が引かれる。
【００９０】
ｉ段目のある頂点とｉ＋１段目のある頂点を結ぶ辺の重みは、ｉ＋１段目の頂点が表す退避路候補上での回復動作完了に要する時間とする。
次最短退避路を決定する際に予め求めた回復時間は、他の退避路候補との干渉を考慮した場合の回復時間である。
そのため、ｓ−ｔ経路中において、最も辺重みの大きい退避路候補が、全てのデッドロックを回復させる上で最も時間のかかるデッドロックとなる。
【００９１】
以上から、退避路組み合わせ方法は、図３５に示すフローチャートに従い動作する。
まず、退避路候補の組み合わせがまだ求まっていないデッドロック群を１つ選ぶ。
選択したデッドロック群を構成するデッドロックを、デッドロック群の右端から順にＤ1，Ｄ2，…，Ｄmとする。
【００９２】
ｍ＝１の場合、ｒR1，ｒL1のうち、回復時間の小さい方を退避路として選択して、他のデッドロック群の退避路候補の選択を行う。
ｍ＞１の場合、左端から順にｒR′i，ｒL′iの回復時間を求める。
ただし、ｒR′1，ｒL′mは存在しないため無視する。
【００９３】
各次最短退避路コストが求まったら、上記の規則に従い多段ネットワークを構成する。
構成した多段ネットワークにおいて、あるｓ−ｔ経路中に存在する各辺の中で最大の重みを持つ辺の値が、最小となるよう経路を選択する。
選択した経路に従い、移動体を退避させる。
この操作を、全てのデッドロック群に対して行う。
【００９４】
具体例として、図３６に示す例おいて、上記退避路組み合わせ方法を実行すると、まずデッドロックＤ1，Ｄ2，Ｄ3から成るデッドロック群ＤＧ1が構成される。
デッドロック群ＤＧ1における退避路の組み合わせを以下の手順により求める。
デッドロックＤ1の右方最短退避路は存在しないため重み無限大（∞）とし、デッドロックＤ2の右方最短退避路はｒVE5,i、デッドロックＤ3の右方最短退避路はｒVE3,oとなる。
デッドロックＤ1の左方最短退避路はｒVE5,a、デッドロックＤ2の左方最短退避路はｒVE3,l、デッドロックＤ3の左方最短退避路はVE2,uとなる。
【００９５】
デッドロックＤ2の右方次最短退避路はｒa,i、デッドロックＤ3の右方次最短退避路はｒVE4,oとなる、
デッドロックＤ1の左方次最短退避路はｒi,a、デッドロックＤ2の左方次最短退避路はｒVE4,lとなる。
各退避路候補に対して重みを求め、図３７に示す多段ネットワークを構成する。
図３７において、各辺の上の数値は、辺の重みを意味する。
上述した例では、図３７に示す通り、頂点ｓから頂点ｔへの経路において、退避路組み合わせとして最大の辺重みが最小となる経路（ｓ，ｒL1，ｒL2，ｒL3，ｔ）が求められる。
【００９６】
（６．５）移動体回復動作部
移動体回復動作部は、図３５に示す通り、退避路組み合わせ方法により求められた退避路組み合わせｒL1，ｒL2，ｒL3に従って回復動作を実行する。
【産業上の利用可能性】
【００９７】
本発明は、デッドロックからの総回復時間を最小きできるように改良した移動体システム及びそのデッドロック回復手法であって、広く産業上利用可能なものである。
【符号の説明】
【００９８】
１０  デッドロック検知部
２０  デッドロック回復部
【図１】
2010176607.tif 000003
【図２】
2010176607.tif 000004
【図３】
2010176607.tif 000005
【図４】
2010176607.tif 000006
【図５】
2010176607.tif 000007
【図６】
2010176607.tif 000008
【図７】
2010176607.tif 000009
【図８】
2010176607.tif 000010
【図９】
2010176607.tif 000011
【図１０】
2010176607.tif 000012
【図１１】
2010176607.tif 000013
【図１２】
2010176607.tif 000014
【図１３】
2010176607.tif 000015
【図１４】
2010176607.tif 000016
【図１５】
2010176607.tif 000017
【図１６】
2010176607.tif 000018
【図１７】
2010176607.tif 000019
【図１８】
2010176607.tif 000020
【図１９】
2010176607.tif 000021
【図２０】
2010176607.tif 000022
【図２１】
2010176607.tif 000023
【図２２】
2010176607.tif 000024
【図２３】
2010176607.tif 000025
【図２４】
2010176607.tif 000026
【図２５】
2010176607.tif 000027
【図２６】
2010176607.tif 000028
【図２７】
2010176607.tif 000029
【図２８】
2010176607.tif 000030
【図２９】
2010176607.tif 000031
【図３０】
2010176607.tif 000032
【図３１】
2010176607.tif 000033
【図３２】
2010176607.tif 000034
【図３３】
2010176607.tif 000035
【図３４】
2010176607.tif 000036
【図３５】
2010176607.tif 000037
【図３６】
2010176607.tif 000038
【図３７】
2010176607.tif 000039