(57)【要約】【課題】高い精度および計算効率を達成する、周囲のスキャンの比較により移動ユニットの相対位置を検出する方法を提供する。【解決手段】計算ユニットが第１のスキャンを反復的に後続のスキャンと比較し、第１のスキャンの時点における位置に対する後続のスキャンのそれぞれの時点における移動ユニットの新たな相対位置を検出し、その都度最後に求められた相対位置を先験情報として考慮する。【選択図】図３
2007042095.tif 000002
【特許請求の範囲】
【請求項１】
周囲のスキャンの比較により移動ユニットの相対位置を検出する方法であって、
−前記移動ユニット（５１０）の周囲のスキャンを継続的に距離センサ（５２０）によって記録してメモリ（５３０）に格納し、
−計算ユニット（５４０）が第１のスキャン（１）を第２のスキャン（２）と比較し、前記第１のスキャン（１）の時点における位置に対する前記第２のスキャン（２）の時点における前記移動ユニット（５１０）の相対位置を検出する、周囲のスキャンの比較により移動ユニットの相対位置を検出する方法において、
前記計算ユニット（５４０）が前記第１のスキャン（１）を反復的に後続のスキャン（３，４）と比較し、前記第１のスキャン（１）の時点における位置に対する後続のスキャン（３，４）のそれぞれの時点における前記移動ユニット（５１０）の新たな相対位置を検出し、その都度最後に求められた相対位置を先験情報として考慮することを特徴とする、周囲のスキャンの比較により移動ユニットの相対位置を検出する方法。
【請求項２】
−前記計算ユニット（５４０）が前記後続のスキャン（３，４）の内の１つを前記第１のスキャン（１）および少なくとも１つの別のスキャンと比較し、その都度暫定的相対位置を検出し、
−前記計算ユニット（５４０）が補正フィルタを用いて、補正された相対位置を前記暫定的相対位置から計算する、請求項１記載の方法。
【請求項３】
前記距離センサ（５２０）はレーザスキャナである、請求項１記載の方法。
【請求項４】
前記補正フィルタは前記暫定的相対位置を平均することによって補正された相対位置を計算する、請求項２記載の方法。
【請求項５】
−前記暫定的相対位置がそれぞれ前記移動ユニット（５１０）の位置に関する確率分布を表す、請求項４記載の方法。
【請求項６】
−少なくとも３つの暫定的相対位置を検出し、前記補正フィルタは相互に同一であるか相似する暫定的相対位置のみを考慮する、請求項２記載の方法。
【請求項７】
−前記先験情報に基づき前記メモリ（５３０）において、前記先験情報に基づき推測される前記移動ユニット（５１０）の目下の位置に相似する先行の位置を有する先行のスキャンを検索し、
−前記先行のスキャンを目下のスキャンと比較し、
−前記比較の際に求められた前記先行のスキャンと前記目下のスキャンとの一致度が所定の閾値を上回る場合には目下の位置を先行の位置として新たに識別する、請求項１記載の方法。
【請求項８】
付加的に絶対位置情報を先験情報として考慮する、請求項１記載の方法。
【請求項９】
反復的に適用し、スキャン組の種々のチェーンを比較する、請求項２記載の方法。
【請求項１０】
前記移動ユニット（５１０）の走行中にオンラインで適用し、常に目下のスキャンを比較する、請求項１記載の方法。
【請求項１１】
−最後に比較された前記後続のスキャン（４）と前記第１のスキャン（１）との重畳度が所定の閾値を下回る場合、前記比較の際に求められたエラー値が所定の閾値を上回る場合、または前記第１のスキャン（１）の時点における前記移動ユニット（５１０）の位置と前記後続のスキャン（４）の時点における前記移動ユニット（５１０）の位置との間の距離が前記距離センサ（５２０）の射程を上回る場合に方法を新たに開始し、
−前記第１のスキャン（１）の代わりに後続の比較の基礎として前記後続のスキャン（４）を使用する、請求項１記載の方法。
【請求項１２】
−前記計算ユニット（５４０）が請求項１から１１までの少なくともいずれか１項記載の方法を選択して実施し、
−目下使用可能な計算リソースを用いて実施可能な方法のみを選択する、請求項１および１０記載の方法。
【請求項１３】
請求項１から１２までのいずれか１項記載の方法を実施する、移動ユニット。
【請求項１４】
プロセッサにおいて処理されると請求項１から１２までのいずれか１項記載の方法を実施する、コンピュータプログラム。
【請求項１５】
コンピュータプログラムがプロセッサにおいて処理されると請求項１から１２までのいずれか１項記載の方法を実施するコンピュータプログラムが記憶されている、コンピュータ読み出し可能なデータ担体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、周囲のスキャンの比較により移動ユニットの相対位置を検出する方法、移動ユニット、コンピュータプログラムおよびコンピュータ読み出し可能なデータ担体に関する。移動ユニットは例えばフォークリフトのような車両またはロボットでよい。
【背景技術】
【０００２】
図５は移動ユニット５１０を示す。移動ユニット５１０は距離センサ５２０、メモリ５３０ならびに計算ユニット５４０を有する。距離センサ５２０は例えばレーザスキャナまたは超音波センサでよい。同等の技術も同様に可能である。
【０００３】
距離センサ５２０によって記録される移動ユニット５１０の周囲のスキャンがメモリ５３０に格納され、計算ユニット５４０によって処理される。
【０００４】
以下説明するスキャンの特性およびスキャンマッチングの方法は当業者には十分に公知であり、また殊に非特許文献１からも公知である。
【０００５】
図１は２つのスキャン１１０，１２０を示す。前述の従来技術から公知であるように、スキャンは移動ユニット５１０の周囲の幾何学的な２次元または３次元のイメージである。スキャンは通常の場合、大量の測定値から構成されており、これらの測定値は例えば極座標で表されている。本明細書においては個々の測定値をスキャンポイントと称する。スキャンポイントを絶対デカルト座標に換算することができる。図１にはそのようにデカルト座標で表したものがスキャン１１０および１２０に関して示されている。スキャン１１０，１２０にはそれぞれ柱１３０および壁１４０が見て取れる。
【０００６】
スキャンマッチングとは、第１のスキャンを例えば第２のスキャンとの最大限の重畳が生じるように回転および移動させることを意味する。図１に示されているケースでは、スキャン１１０との最大限の重畳を達成するためにスキャン１２０を若干時計回りに回転させる必要がある。
【０００７】
スキャン１２０の回転および移動の度合いが求められると、それに基づき相対位置を導出することができ、この相対位置はスキャン１１０の時点に対するスキャン１２０の時点での移動ユニット５１０の相対的な位置および方位を表す。このようにして、反復的なスキャンマッチングにより移動ユニット５１０の局所的な方位を測定することができる。
【０００８】
図２は、従来技術によるスキャンの処理を示す。ここで実施されるスキャンマッチングの範囲において第１のスキャン１と第２のスキャン２の比較１２が行われる。ここで比較１２は従来のスキャンマッチング方法を用いて行われる。比較１２により、第１のスキャン１の時点の位置に対する第２のスキャン２の時点における移動ユニット５１０の相対位置が検出される。このことは実質的に居場所と方位の変化を意味する。続いて第２のスキャン２と後続のスキャン３の比較２３が行われる。ここでは第２のスキャン２の時点の位置に対する後続のスキャン３の時点における移動ユニット５１０の相対位置が検出される。同じやり方で、後続のスキャン３，４，５の比較３４，３５が行われる。この方法は比較を行う毎にエラーが累積されていくので非常に不正確である。
【０００９】
この不正確に基づいて、従来技術から公知である方法では相対位置を検出するための基礎として通常の場合車輪センサが使用されており、時間単位毎の車輪の回転から移動ユニット５１０の速度が検出され、また右側の車輪と左側の車輪の異なる速度から移動ユニット５１０の角速度が検出される。択一的または補完的にインフラストラクチャが頻繁に使用され、例えばＧＰＳ衛星、反射性の帯または磁石が相対位置を検出するために利用される。さらには、目下のセンサ測定を補償調整する地図も頻繁に使用される。
【００１０】
さらに従来技術からは、これらの情報に基づき周囲のスキャンの比較から移動ユニットの相対位置を検出する方法が公知である。しかしながら相対位置を検出するためのそのような方法は他のセンサの付加的な情報、例えばオドメトリによる付加的な情報を常に必要とし、これらの情報がそれぞれの方法により質的に改善される。すなわち従来技術においては、スキャンマッチングから計算される相対移動が、例えば車輪を基礎とするオドメトリの精度を改善するために使用される。
【００１１】
前述の方法の欠点は、例えば車輪センサをシステムアップしなければならないような場合にもそのような車輪センサは高価であり、またインフラストラクチャまたは地図データのような代替手段を使用できないことが多い、または少なくとも部分的にしか使用できないということである。さらには公知の方法は非常に不正確なことが多い。殊にスキャンマッチングの際に過度に多くのエラーが累積される。確かにスキャンマッチングにおけるエラーを最小にすることができる方法が公知であるが、それらの方法は二次の複雑度（quadraic complexity）を有するのでオフラインでしか使用することができない。すなわち方位を決定する移動ユニットの走行中にはこれらの方法を使用することができない。
【非特許文献１】Gutmann, Jens-Steffen著「Robuste Navigation autonomer mobiler Systeme, Dissertationen zur kuenstlichen Intelligenz」第２４１巻、Berlin: Akademische Verlagsgesellschaft Aka GmbH、２０００年、第２１頁〜８８頁
【発明の開示】
【発明が解決しようとする課題】
【００１２】
したがって本発明の課題は、高い精度および計算効率を達成する、周囲のスキャンの比較により移動ユニットの相対位置を検出する方法、移動ユニット、コンピュータプログラムならびにコンピュータ読み出し可能データ担体を提供することである。
【課題を解決するための手段】
【００１３】
周囲のスキャンの比較により移動ユニットの相対位置を検出する方法に関する課題は、計算ユニットが第１のスキャンを反復的に後続のスキャンと比較し、第１のスキャンの時点における位置に対する後続のスキャンのそれぞれの時点における移動ユニットの新たな相対位置を検出し、その都度最後に求められた相対位置を先験情報として考慮することによって解決される。
【００１４】
移動ユニットに関する課題は、移動ユニットが請求項１から１２までのいずれか１項記載の方法を実施することによって解決される。
【００１５】
コンピュータプログラムに関する課題は、コンピュータプログラムがプロセッサにおいて処理されると請求項１から１２までのいずれか１項記載の方法を実施することによって解決される。
【００１６】
コンピュータ読み出し可能なデータ担体に関する課題は、コンピュータプログラムがプロセッサにおいて処理されると請求項１から１２までのいずれか１項記載の方法を実施するコンピュータプログラムが記憶されていることによって解決される。
【発明を実施するための最良の形態】
【００１７】
周囲のスキャンの比較によって移動ユニットの相対位置を検出する方法においては、移動ユニットの周囲の連続的なスキャンが距離センサによって記録され、メモリに格納される。 
さらに計算ユニットが第１のスキャンを第２のスキャンと比較し、この際第１のスキャン１の時点における移動ユニットの位置に対する第２のスキャン２の時点における移動ユニットの相対位置が検出される。
【００１８】
本方法は、計算ユニットが第１のスキャンを反復的に後続のスキャンと比較し、この際第１のスキャンの時点の位置に対する後続のスキャンそれぞれの時点における移動ユニットの新たな相対位置が検出され、その都度最後に求められた相対位置が先験情報として考慮される。
【００１９】
移動ユニットは前述の方法を実施するよう設けられている。
【００２０】
コンピュータプログラムは、このコンピュータプログラムがプロセッサにおいて処理されると前述の方法を実施する。
【００２１】
コンピュータ読み出し可能データ担体は、コンピュータプログラムがプロセッサにおいて処理されると前述の方法を実施するコンピュータプログラムを記憶している。
【００２２】
その都度最後に求められた相対位置を先験情報として考慮することにより、他の比較に基づく先験位置評価と関連させて個々のスキャンが十分に一致する場合には、目下の比較の不正確は比較的長い期間にわたっても増加しないという事実を利用することができる。この場合には従来技術よりも有利である。何故ならば従来技術ではスキャンを順次比較する際に相対位置の検出時の不正確が即座に加算され、結果が利用できなくなるからである。殊に、その都度最後に求められた相対位置を先験情報として考慮することによって、スキャンを長い期間にわたり効率的かつ確実に比較し、正確な相対位置を検出することができる。
【００２３】
本方法はＧＰＳ衛星、反射性の帯または磁石のようなインフラストラクチャも、周囲の地図も必要としない。したがって設備のコストが掛かることなく本方法を即座に使用できる状態にあり、また例えば倉庫のような環境が変化する場所においても機能することができる。本方法は、オドメトリデータを省略できるほどの高精度を達成する。したがって場合によっては、車輪センサの比較的高価なシステムアップは必要ない。スキャンマッチングのみによる本方法の高い精度は、前述の付加的なセンサ情報または地図データが確かに提供されるが、完全なものではない、または時折使用できない場合であっても決定的な利点を提供する。
【００２４】
１つの実施形態によれば計算ユニットは後続のスキャンを第１のスキャンおよび少なくとも１つの別のスキャンと比較し、この際その都度暫定的相対位置が検出される。補正フィルタを用いることにより続いて計算ユニットは補正された相対位置を暫定的相対位置から計算する。
【００２５】
この実施形態は、各相対運動をスキャン組の種々のチェーンから計算することができるという事実を使用する。暫定的相対位置を補償調整することによってエラーを識別、低減、除去または発見することができる。
【００２６】
１つの実施形態によれば距離センサはレーザスキャナである。
【００２７】
例えば超音波のような別の距離センサも考えられる。レーザスキャナは殊に高い精度および信頼度の点で優れている。
【００２８】
１つの実施形態においては、補正フィルタが暫定的相対位置を平均することによって補正された相対位置を計算する。
【００２９】
この実施形態は、暫定的相対位置が相似している場合には有利である。
【００３０】
有利な実施形態においては、それぞれの暫定的相対位置が移動ユニットの位置に関する確率分布を表す。そのような確率分布を正規分布の場合には例えば楕円によって表すことができ、またカルマンフィルタによって平均することができる。
【００３１】
このことはスキャンマッチングが不正確を例えば共分散マトリクスの形で提供する場合にはまさに有利である。
【００３２】
別の実施形態においては少なくとも３つの暫定的相対位置が検出され、これらの暫定的相対位置を基礎として補正フィルタは相互に同一であるか相似する暫定的相対位置のみを考慮する。
【００３３】
これによって、大きなエラーを有する暫定的相対位置を破棄することができる。
【００３４】
１つの実施形態によれば、先験情報に基づきメモリにおいては、先験情報に基づき推測される移動ユニットの目下の位置に相似する先行の位置を有する先行のスキャンが検索される。続いて先行のスキャンが目下のスキャンと比較される。比較の際に求められた先行のスキャンと目下のスキャンとの一致度が所定の閾値を上回る場合には、目下の位置が先行の位置として新たに識別される。
【００３５】
この実施形態は比較されるスキャンが時間的に十分離れていても良いという利点を提供する。数百のスキャンを比較することができる。複数の先行のスキャンを検索し、目下のスキャンと比較することができる。
【００３６】
別の実施形態によれば、付加的に絶対位置情報が先験情報として考慮される。
【００３７】
この場合には絶対位置情報の精度および使用可能性に対する要求を低減することができる。したがって、インフラストラクチャまたは地図データを提供するコストは低減される。
【００３８】
１つの実施形態においては本方法が反復的に適用され、これによってスキャン組の種々のチェーンが比較される。
【００３９】
このような反復は、エラーが累積されることなく本方法を継続的に適用することができるという利点を提供する。
【００４０】
別の実施形態においては本方法が移動ユニットの走行中にオンラインで適用され、この場合には目下のスキャンが常に比較される。
【００４１】
この実施形態はリアルタイムでの相対位置の検出を実現し、これによって移動ユニットの方位を運転時に決めることができる。
【００４２】
１つの実施形態においては、最後に比較された後続のスキャンと第１のスキャンとの重畳度が所定の閾値を下回る場合、比較の際に求められたエラー値が所定の閾値を上回る場合、または第１のスキャンの時点における移動ユニットの位置と後続のスキャンの時点における移動ユニットの位置との間の距離が距離センサの射程を上回る場合には本方法が新たに開始される。第１のスキャンの代わりに後続の比較のための基礎として後続のスキャンが使用される。
【００４３】
有利な実施形態においては、計算ユニットが前述の構成および実施形態に応じた少なくとも１つの方法を選択して実施する。目下のところ使用できる計算リソースを用いて実施することができる方法のみが選択される。
【００４４】
このことは、残存の計算リソースを最適に使用することができるという利点を提供する。相対位置の検出の精度を高めるために、本方法の前述の実施形態が選択的に実施される。
【実施例】
【００４５】
図１，２および５は従来技術を検討した際に既に説明した。
【００４６】
図３は１つの実施例を示す。ここでは第１のスキャン１が第２のスキャン２と比較１２される。この際、第１のスキャン１の時点における移動ユニット５１０（図５を参照されたい）の位置に対する第２のスキャン２の時点における移動ユニット５１０の相対位置が検出される。求められた相対位置は中間結果としてメモリ５３０（図５を参照されたい）に格納される。続いて第１のスキャン１が再び比較されるが、ここでは後続のスキャン３との比較が行われる。この際に、中間結果として記憶されている最後に求められた相対位置が先験情報として考慮される。
【００４７】
どのようにしてそのような考慮を実施することができるかは従来技術から十分公知である。検索領域が縮小されるかデータ量が低減されることによって曖昧さが除去され、また本方法の効率が高められる。先験情報の考慮下で殊に考えられる相対位置のみをスキャンマッチングの際に考慮すればよい。さらには、最後に求められた相対位置の先験情報に従い覆われているであろうと推測される後続のスキャン３におけるスキャンポイント、またはこの後続のスキャン３の記録領域内には存在する可能性の無いスキャンポイントを第１のスキャンから除去するために、例えば投影フィルタを使用することができる。
【００４８】
後続のステップにおいては第１のスキャン１と後続のスキャン４の比較１４が行われる。ここでもやはり最後に求められた相対位置、この場合には比較１３において求められた相対位置が先験情報として考慮される。したがって先験情報はスキャンマッチングの品質および効率を著しく改善する位置評価のための１つの手段である。図３に示されているように、ここでは例えば後続のスキャン４を基礎として新たな一連のスキャン比較が開始される。このようにして本方法を、継続的に、殊に移動ユニット５１０の運転時ないし走行中にも適用できるようにするために反復的に実施することができる。
【００４９】
図４は別の実施例を示す。ここでは第１のスキャン１、第２のスキャン２ならびに後続のスキャン３，４，５が前述の実施例と同様に比較される。しかしながら付加的に、第２のスキャン２と後続のスキャン４の比較２４が行われる。比較１４および２４において求められた相対位置がここでは暫定的相対位置と見なされる。続いて補正フィルタを用いることにより、補正された相対位置が暫定的相対位置から計算される。
【００５０】
例えば補正フィルタは２つの暫定的相対位置を平均することができる。平均値はエラーを低減することができる。スキャンの別の組を形成して比較することも可能であり、これによって付加的な暫定的相対位置を平均のために使用することができる。
【００５１】
スキャンマッチングの範囲においては不正確が一緒に提供されることが多く、このような不正確は例えば共分散マトリクスとして表すことができる。移動ユニット５１０の位置に関する確率分布は、正規分布の場合デカルト座標で楕円として表すことができる。この楕円を例えばカルマンフィルタを介して相互に計算して平均することができる。確率分布の種類に依存して他のフィルタ、例えば拡張カルマンフィルタを選択することもできる。
【００５２】
図６はスキャン６１０および６２０をデカルト座標で壁１４０および柱１３０と共に示している。ここでは楕円６１５および６２５が記入されており、これらの楕円６１５および６２５はスキャンマッチング方法の範囲において相対位置に関して求めることができるような移動ユニット５１０の位置に関する確率分布をそれぞれ表している。
【００５３】
択一的な実施例においては、少なくとも３つの暫定的相対位置が種々の組およびスキャンならびにそれぞれの比較から形成される。図４に示されている比較１４および２４に付加的に、例えば第１のスキャン１を後続のスキャン４とさらに比較してもよい。これにより後続のスキャン４の時点における移動ユニット５１０の相対位置を検出するために３つの暫定的相対位置を使用することができる。これらの暫定的相対位置の内の１つが明らかに他の２つの暫定的相対位置とは異なる場合には、対応する比較においてエラーが発生していることが想定される。この場合には相応の暫定的相対位置が破棄され、その結果補正フィルタは他の２つの暫定的相対位置のみを考慮する。例えば残りの暫定的相対位置を相互に平均することによって、補正された相対位置を計算することができる。
【００５４】
本方法は暫定的相対位置自体の一致またはずれに基づいて、これらの暫定的相対位置が平均されるべきか破棄されるべきかを決定することもできる。
【００５５】
時間的に十分離れた２つのスキャンを比較することによって、移動ユニット５１０は既に訪れた場所を再度検出することができる。すなわち移動ユニット５１０が先行するスキャンの時点における場所とび同じ場所に再び居る場合には、目下のスキャンとの比較は殊に高い一致度を供給することになる。これに関してメモリ５３０においては先験情報を基礎として、この先験情報に基づき推測される移動ユニット５１０の目下の位置に相似する先行の位置を有する先行のスキャンが検索される。これに続いて先行のスキャンが目下のスキャンと比較される。一致度が所定の閾値を上回ると、古い位置が再び識別される。
【００５６】
前述の相対位置の検出に付加的に、本方法においては絶対的な位置情報も先験情報の範囲において使用される。絶対的な位置情報を例えばインフラストラクチャ（ＧＰＳ衛星、反射性の帯または磁石など）または地図を介して提供することができる。
【００５７】
１つの実施例によればスキャンマッチングが反復的に継続的に適用され、これによってスキャン組の種々のチェーンが比較される。このことは図４に示唆されている。つまり、後続のスキャン４が後続のスキャン５とのさらなる比較のための基礎を提供している。スキャンマッチングを反復的に適用することによって、本方法を移動ユニット５１０の走行中にオンラインでも適用することができ、この際移動ユニット５１０の周囲の目下のスキャンが常に比較に関与し、また移動ユニット５１０の目下の相対位置がこの移動ユニット５１０の方位を決めるために検出される。
【００５８】
比較されるスキャン組のチェーンを形成することによって、スキャンマッチング方法のアルゴリズム的な複雑性は低減させることができる。何故ならば、必要とされる比較の回数は少なく保たれるからである。これによって移動ユニット５１０の走行中のオンラインの適用が可能となる。これに対して全てのスキャンを相互に比較しようとした場合、相応のアルゴリズムは二次の複雑度を有することになり、したがってそのようなアルゴリズムはオフラインでのみしか実行できない。
【００５９】
図３および図４に示されているように、最後に比較された後続のスキャン４と第１のスキャン１との重畳度が所定の閾値を下回る場合、比較の際に求められたエラー値が所定の閾値を上回る場合、または第１のスキャンの時点における移動ユニット５１０の位置と後続のスキャン４の時点における移動ユニット５１０の位置との間の距離が距離センサの射程を上回る場合には本方法が新たに開始される。第１のスキャン１の代わりに後続の比較のための基礎として後続のスキャン４が使用される。
【００６０】
目下使用できる計算リソースに依存して、計算ユニット５４０は相対位置を可能な限り最善の精度で、それにもかかわらずリアルタイムで計算するために、前述の実施例の中から個々の実施形態を選択または省略することができる。
【図面の簡単な説明】
【００６１】
【図１】２つのスキャン。
【図２】従来技術によるスキャンマッチング方法。
【図３】先験位置評価を用いるスキャンマッチング方法。
【図４】先験位置評価を用いるスキャンマッチング方法。
【図５】移動ユニット。
【図６】楕円を含む２つのスキャン。
【図１】
2007042095.tif 000003
【図２】
2007042095.tif 000004
【図３】
2007042095.tif 000005
【図４】
2007042095.tif 000006
【図５】
2007042095.tif 000007
【図６】
2007042095.tif 000008