JPH05101035A - 移動ロボツトの最適経路探索方法 - Google Patents
移動ロボツトの最適経路探索方法Info
- Publication number
- JPH05101035A JPH05101035A JP10611191A JP10611191A JPH05101035A JP H05101035 A JPH05101035 A JP H05101035A JP 10611191 A JP10611191 A JP 10611191A JP 10611191 A JP10611191 A JP 10611191A JP H05101035 A JPH05101035 A JP H05101035A
- Authority
- JP
- Japan
- Prior art keywords
- node
- route
- evaluation
- nodes
- mobile robot
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Landscapes
- Control Of Conveyors (AREA)
- Control Of Position, Course, Altitude, Or Attitude Of Moving Bodies (AREA)
- Management, Administration, Business Operations System, And Electronic Commerce (AREA)
Abstract
(57)【要約】
【目的】 移動ロボットの最適経路を探索するに際し、
回り道となる経路を選択する危険性を低減する。 【構成】 分岐ノードにおいて、次の分岐ノードまでの
各経路の総合評価に基づいて当該分岐ノードから進むべ
き経路を選択する。
回り道となる経路を選択する危険性を低減する。 【構成】 分岐ノードにおいて、次の分岐ノードまでの
各経路の総合評価に基づいて当該分岐ノードから進むべ
き経路を選択する。
Description
【０００１】
【産業上の利用分野】この発明は、自立無人車等の移動
ロボットに適用して好適な移動ロボットの最適経路探索
方法に関する。
ロボットに適用して好適な移動ロボットの最適経路探索
方法に関する。
【０００２】
【従来の技術】移動ロボットシステムを効率的に動作さ
せるためには、移動ロボットを現在地から目的地に移動
させる際、常に移動ロボットが時間的損失の最小な最適
な経路を辿るようにする必要がある。そこで、地図上の
２点間の最適経路を探索する問題について種々の研究が
なされ、この問題を解く各種方法が提案された。例え
ば、移動ロボットに内蔵されたメモリに、地図上に存在
する各ノード間の直線距離や各ノード間の接続関係を示
すデータを格納しておき、これらのデータに基づき、現
在位置ノードＶｉから次に進むべきノードＶｊを決定す
る方法が提案されている。この最適経路探索方法は以下
説明する手順に従って進められる。 （１）縦型探索、横型探索等の公知の手法によって、出
発ノードＳから目的ノードＧに至る各経路を探索する。
そして、中間ノードＶｉに接続されたノードの中から次
に進むべきノードＶｊの候補ノードＶｊｘ（ｘ＝１，
２，…）を選択する。 （２）現在位置ノードＶｉから各候補ノードＶｊｘに進
む各移動動作について評価を行い、最も評価値の高いノ
ードＶｊを選ぶ。 （３）この操作を目的ノードＧに到達するまで繰り返
す。
せるためには、移動ロボットを現在地から目的地に移動
させる際、常に移動ロボットが時間的損失の最小な最適
な経路を辿るようにする必要がある。そこで、地図上の
２点間の最適経路を探索する問題について種々の研究が
なされ、この問題を解く各種方法が提案された。例え
ば、移動ロボットに内蔵されたメモリに、地図上に存在
する各ノード間の直線距離や各ノード間の接続関係を示
すデータを格納しておき、これらのデータに基づき、現
在位置ノードＶｉから次に進むべきノードＶｊを決定す
る方法が提案されている。この最適経路探索方法は以下
説明する手順に従って進められる。 （１）縦型探索、横型探索等の公知の手法によって、出
発ノードＳから目的ノードＧに至る各経路を探索する。
そして、中間ノードＶｉに接続されたノードの中から次
に進むべきノードＶｊの候補ノードＶｊｘ（ｘ＝１，
２，…）を選択する。 （２）現在位置ノードＶｉから各候補ノードＶｊｘに進
む各移動動作について評価を行い、最も評価値の高いノ
ードＶｊを選ぶ。 （３）この操作を目的ノードＧに到達するまで繰り返
す。
【０００３】
【発明が解決しようとする課題】ところで、上述した最
適経路探索方法により最適経路探索を行った場合、分岐
点ノードおよびこれに直接接続された各次候補ノードに
対して行われる評価のみによって次に進むべきノードが
決定されるので、最適でない経路が探索されてしまうこ
とがあるという問題があった。例えば、図２において、
出発ノードＳから分岐ノード１に進むと、ノード２ある
いは５のいずれかを選択することとなる。ここで、ノー
ド２に進むと方向転換による損失を伴うこととなる。し
かし、この損失がノード２に進む場合の評価値を下げた
としても、目的ノードＧまでの距離に関連した項が評価
値を高めるのに有効に作用すると、ノード２が選択され
ることとなる。しかし、一旦、ノード２が選択されてし
まうと、結局、最適でない経路Ｓ、１、２、３、４、
６、７、８、９、Ｇが探索されてしまう。この場合にお
ける最適経路は、Ｓ、１、５、６、７、８、９、Ｇであ
る。この発明は上述した事情に鑑みてなされたものであ
り、回り道となってしまう経路を選択することがなく、
最適経路をより的確に探索し得る移動ロボットの最適経
路探索方法を提供することを目的とする。
適経路探索方法により最適経路探索を行った場合、分岐
点ノードおよびこれに直接接続された各次候補ノードに
対して行われる評価のみによって次に進むべきノードが
決定されるので、最適でない経路が探索されてしまうこ
とがあるという問題があった。例えば、図２において、
出発ノードＳから分岐ノード１に進むと、ノード２ある
いは５のいずれかを選択することとなる。ここで、ノー
ド２に進むと方向転換による損失を伴うこととなる。し
かし、この損失がノード２に進む場合の評価値を下げた
としても、目的ノードＧまでの距離に関連した項が評価
値を高めるのに有効に作用すると、ノード２が選択され
ることとなる。しかし、一旦、ノード２が選択されてし
まうと、結局、最適でない経路Ｓ、１、２、３、４、
６、７、８、９、Ｇが探索されてしまう。この場合にお
ける最適経路は、Ｓ、１、５、６、７、８、９、Ｇであ
る。この発明は上述した事情に鑑みてなされたものであ
り、回り道となってしまう経路を選択することがなく、
最適経路をより的確に探索し得る移動ロボットの最適経
路探索方法を提供することを目的とする。
【０００４】
【課題を解決するための手段】この発明による最適経路
探索方法は、予め記憶された地図情報に基づいて経路を
決定して走行する移動ロボットにおいて、経路探索中、
分岐ノードに到達した場合、次に進むべきノードを次の
分岐ノードまでの評価に従って決定することを特徴とす
る。
探索方法は、予め記憶された地図情報に基づいて経路を
決定して走行する移動ロボットにおいて、経路探索中、
分岐ノードに到達した場合、次に進むべきノードを次の
分岐ノードまでの評価に従って決定することを特徴とす
る。
【０００５】
【作用】上記方法によれば、分岐ノードとこれに接続さ
れる各分岐ノードとの間の各経路に対して総合評価が行
われ、この総合評価の結果に基づいて当該分岐ノードか
ら進むべき次のノードが決定される。このように経路選
択の際の評価の対象を広範囲のノードに拡張したので、
回り道となる経路を選択する危険性が減少する。
れる各分岐ノードとの間の各経路に対して総合評価が行
われ、この総合評価の結果に基づいて当該分岐ノードか
ら進むべき次のノードが決定される。このように経路選
択の際の評価の対象を広範囲のノードに拡張したので、
回り道となる経路を選択する危険性が減少する。
【０００６】
【実施例】以下、図面を参照し、本発明の一実施例によ
る移動ロボットの最適経路探索方法について説明する。
図１は同最適経路探索方法を適用した移動ロボットの構
成を示すブロック図である。この図において、２１は移
動ロボットの走行装置であり、走行装置２１には、その
走行制御を行うＣＰＵ（中央処理装置）２２が接続され
ている。また、ＣＰＵ２２にはメモリ２３が接続され、
このメモリ２３には、図２によって例示された各ノード
の座標、各ノード間の接続関係を示す地図データが格納
されている。ＣＰＵ２２は、外部の制御局からの作業指
示（目的ノードＧおよびその目的ノードＧにて行うべき
作業）を受信する。そして、メモリ２３に記憶された地
図データを参照し、出発ノードＳから目的ノードＧに至
る最適経路を探索する。
る移動ロボットの最適経路探索方法について説明する。
図１は同最適経路探索方法を適用した移動ロボットの構
成を示すブロック図である。この図において、２１は移
動ロボットの走行装置であり、走行装置２１には、その
走行制御を行うＣＰＵ（中央処理装置）２２が接続され
ている。また、ＣＰＵ２２にはメモリ２３が接続され、
このメモリ２３には、図２によって例示された各ノード
の座標、各ノード間の接続関係を示す地図データが格納
されている。ＣＰＵ２２は、外部の制御局からの作業指
示（目的ノードＧおよびその目的ノードＧにて行うべき
作業）を受信する。そして、メモリ２３に記憶された地
図データを参照し、出発ノードＳから目的ノードＧに至
る最適経路を探索する。
【０００７】以下、図２に示す場合を例に本実施例によ
る最適経路の探索方法を説明する。経路探索中、分岐ノ
ードＶｉ（例えばノード１）に至ったとする。この場
合、現在ノードＶｉとこれに接続される次の分岐ノード
（例えばノード６）との間の各経路に対する総合評価を
行う。この総合評価において、各ノード間の移動に対す
る評価は次のようにして行う。すなわち、現在ノードＶ
ｉおよび次候補ノードＶｊｘに対し、下記式に示す評価
関数Ｈ（Ｖｉ，Ｖｊｘ）を適用し、現在ノードＶｉおよ
び次候補ノードＶｊｘ間の移動に対する評価を行う。
る最適経路の探索方法を説明する。経路探索中、分岐ノ
ードＶｉ（例えばノード１）に至ったとする。この場
合、現在ノードＶｉとこれに接続される次の分岐ノード
（例えばノード６）との間の各経路に対する総合評価を
行う。この総合評価において、各ノード間の移動に対す
る評価は次のようにして行う。すなわち、現在ノードＶ
ｉおよび次候補ノードＶｊｘに対し、下記式に示す評価
関数Ｈ（Ｖｉ，Ｖｊｘ）を適用し、現在ノードＶｉおよ
び次候補ノードＶｊｘ間の移動に対する評価を行う。
【数１】 上記数１において、Ａ（Ｖｊｘ，Ｇ）は次候補ノードＶ
ｊｘと目的ノードＧとの距離によって定まる損失項、Ｂ
（Ｖｉ，Ｖｊ）は現在ノードＶｉと次候補ノードＶｊｘ
との間の距離によって定まる損失項である。また、Ｃ
（θ）はノードＶｉにおける進行方向（すなわち、前回
ノードと現在ノードＶｉとを結ぶ線分の方向）と、ノー
ドＶｉ，Ｖｊを結ぶ線分とがなす角度θによって定まる
損失項である。また、Ｗａ，ＷｂおよびＷｃは各々重み
付けのための係数である。ただし、次候補ノードＶｊｘ
が分岐ノードでない場合は、上記数１においてＷａ＝０
とした評価関数により評価を行う。これは、分岐ノード
でないノードに対しては、目的ノードとの距離を考慮し
た評価を行う意味がないからである。このようにして得
られる各ノード間の移動の評価値を加算することによ
り、分岐ノード間の各経路の総合評価を行い、総合評価
値に基づいて経路の選択を行う。
ｊｘと目的ノードＧとの距離によって定まる損失項、Ｂ
（Ｖｉ，Ｖｊ）は現在ノードＶｉと次候補ノードＶｊｘ
との間の距離によって定まる損失項である。また、Ｃ
（θ）はノードＶｉにおける進行方向（すなわち、前回
ノードと現在ノードＶｉとを結ぶ線分の方向）と、ノー
ドＶｉ，Ｖｊを結ぶ線分とがなす角度θによって定まる
損失項である。また、Ｗａ，ＷｂおよびＷｃは各々重み
付けのための係数である。ただし、次候補ノードＶｊｘ
が分岐ノードでない場合は、上記数１においてＷａ＝０
とした評価関数により評価を行う。これは、分岐ノード
でないノードに対しては、目的ノードとの距離を考慮し
た評価を行う意味がないからである。このようにして得
られる各ノード間の移動の評価値を加算することによ
り、分岐ノード間の各経路の総合評価を行い、総合評価
値に基づいて経路の選択を行う。
【０００８】図２に例示する場合、分岐ノード１まで探
索が進むと、上記数１の評価関数においてＷａ＝０とし
て評価関数に従い、ノード１および２間の移動、ノード
２および３間の移動、ノード３および４間の移動に対す
る各評価値と演算する。そして、上記数１の評価関数に
よりノード４および６間の移動に対する評価値を演算す
る。このようにして得られた各評価値を加算し、ノード
１、２、３、４、６を通過する経路の総合評価値を求め
る。同様の方法により、ノード１および５間の移動、ノ
ード５および６間の移動に対する各評価値を演算して加
算し、ノード１、５、６を通過する経路の総合評価値を
求める。そして、総合評価値の高い方の経路を選択す
る。この経路が選択されることにより、分岐ノード６ま
での経路探索も同時に終了する。
索が進むと、上記数１の評価関数においてＷａ＝０とし
て評価関数に従い、ノード１および２間の移動、ノード
２および３間の移動、ノード３および４間の移動に対す
る各評価値と演算する。そして、上記数１の評価関数に
よりノード４および６間の移動に対する評価値を演算す
る。このようにして得られた各評価値を加算し、ノード
１、２、３、４、６を通過する経路の総合評価値を求め
る。同様の方法により、ノード１および５間の移動、ノ
ード５および６間の移動に対する各評価値を演算して加
算し、ノード１、５、６を通過する経路の総合評価値を
求める。そして、総合評価値の高い方の経路を選択す
る。この経路が選択されることにより、分岐ノード６ま
での経路探索も同時に終了する。
【０００９】
【発明の効果】以上説明したように、この発明による最
適経路探索方法によれば、予め記憶された地図情報に基
づいて経路を決定して走行する移動ロボットにおいて、
経路探索中、分岐ノードに到達した場合、次に進むべき
ノードを次の分岐ノードまでの評価に従って決定するの
で、回り道となる経路を選択する危険性が減少し、より
的確に最適回路を探索することができるという効果があ
る。
適経路探索方法によれば、予め記憶された地図情報に基
づいて経路を決定して走行する移動ロボットにおいて、
経路探索中、分岐ノードに到達した場合、次に進むべき
ノードを次の分岐ノードまでの評価に従って決定するの
で、回り道となる経路を選択する危険性が減少し、より
的確に最適回路を探索することができるという効果があ
る。
【図１】 この発明の一実施例による最適経路探索方法
を適用した移動ロボットの構成を示すブロック図であ
る。
を適用した移動ロボットの構成を示すブロック図であ
る。
【図２】 移動ロボットの走行路を例示する図である。
Ｃ……制御局、Ｒ１〜Ｒｎ……移動ロボット。
Claims (1)
- 【請求項１】 予め記憶された地図情報に基づいて経路
を決定して走行する移動ロボットにおいて、 経路探索中、分岐ノードに到達した場合、次に進むべき
ノードを次の分岐ノードまでの評価に従って決定するこ
とを特徴とする移動ロボットの最適経路探索方法。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP10611191A JPH05101035A (ja) | 1991-05-10 | 1991-05-10 | 移動ロボツトの最適経路探索方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP10611191A JPH05101035A (ja) | 1991-05-10 | 1991-05-10 | 移動ロボツトの最適経路探索方法 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH05101035A true JPH05101035A (ja) | 1993-04-23 |
Family
ID=14425364
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP10611191A Pending JPH05101035A (ja) | 1991-05-10 | 1991-05-10 | 移動ロボツトの最適経路探索方法 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH05101035A (ja) |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2009020749A (ja) * | 2007-07-12 | 2009-01-29 | Toshiba Corp | ロボット制御装置及び方法 |
| US8045418B2 (en) | 2006-03-29 | 2011-10-25 | Kabushiki Kaisha Toshiba | Position detecting device, autonomous mobile device, method, and computer program product |
| US12384417B2 (en) * | 2022-12-21 | 2025-08-12 | Guangdong Polytechnic Normal University | Path optimization method and system for mobile robot |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS6232516A (ja) * | 1985-08-06 | 1987-02-12 | Shinko Electric Co Ltd | 移動ロボツトの最適経路探索方法 |
| JPH02105972A (ja) * | 1988-10-14 | 1990-04-18 | Nippon Telegr & Teleph Corp <Ntt> | ルート探索装置 |
-
1991
- 1991-05-10 JP JP10611191A patent/JPH05101035A/ja active Pending
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS6232516A (ja) * | 1985-08-06 | 1987-02-12 | Shinko Electric Co Ltd | 移動ロボツトの最適経路探索方法 |
| JPH02105972A (ja) * | 1988-10-14 | 1990-04-18 | Nippon Telegr & Teleph Corp <Ntt> | ルート探索装置 |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US8045418B2 (en) | 2006-03-29 | 2011-10-25 | Kabushiki Kaisha Toshiba | Position detecting device, autonomous mobile device, method, and computer program product |
| JP2009020749A (ja) * | 2007-07-12 | 2009-01-29 | Toshiba Corp | ロボット制御装置及び方法 |
| US12384417B2 (en) * | 2022-12-21 | 2025-08-12 | Guangdong Polytechnic Normal University | Path optimization method and system for mobile robot |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN113485369B (zh) | 改进a*算法的室内移动机器人路径规划和路径优化方法 | |
| CN106647769B (zh) | 基于a*提取引导点的agv路径跟踪与避障协调方法 | |
| US11953912B2 (en) | Traveling down a prescribed arrangement of paths with a mobile robot | |
| US10576976B2 (en) | Drivable area setting device and drivable area setting method | |
| CN112683278A (zh) | 一种基于改进a*算法和贝塞尔曲线的全局路径规划方法 | |
| CN109542098A (zh) | 一种基于最小转弯代价的agv路径规划方法 | |
| KR20170088228A (ko) | 다중로봇의 자기위치인식에 기반한 지도작성 시스템 및 그 방법 | |
| CN107631734A (zh) | 一种基于D*_lite算法的动态平滑路径规划方法 | |
| JP3269418B2 (ja) | 最適経路探索方法 | |
| CN115167398A (zh) | 一种基于改进a星算法的无人船路径规划方法 | |
| CN117553804B (zh) | 路径规划方法、装置、计算机设备和存储介质 | |
| Zhang et al. | A robust reference path selection method for path planning algorithm | |
| JP2016149090A (ja) | 自律移動装置、自律移動システム、自律移動方法、およびプログラム | |
| US20250153821A1 (en) | Control method applied in underwater robot, underwater robot, and storage medium | |
| CN116878527A (zh) | 一种基于改进自适应窗口算法的混合路径规划方法及装置 | |
| JPH04365104A (ja) | 最適化経路計画装置及び自律移動ロボット | |
| JP5732921B2 (ja) | 移動体マップ装置、その処理方法及びプログラム | |
| Benelmir et al. | An efficient autonomous vehicle navigation scheme based on LiDAR sensor in vehicular network | |
| JPH05101035A (ja) | 移動ロボツトの最適経路探索方法 | |
| CN116149314A (zh) | 机器人全覆盖作业方法、装置及机器人 | |
| CN116225020A (zh) | 一种基于改进a*算法的多航点自主规划最优路径的方法 | |
| JPH0731667B2 (ja) | 移動ロボツトの最適経路探索方法 | |
| JPS6232519A (ja) | 移動ロボツトシステムにおける最適経路探索方法 | |
| JPS6232516A (ja) | 移動ロボツトの最適経路探索方法 | |
| JPH04340607A (ja) | 最適経路決定装置 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A02 | Decision of refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A02 Effective date: 19980818 |