【免费】5.Topologicalsimultaneouslocalizationandmapping(SLAM)towardexactlocalizationwithoutexplicitlocalization资源-CSDN文库

需积分: 0 4 浏览量 2010-04-07 20:29:24 上传评论收藏 217KB PDF 举报

资源详情

资源评论

资源推荐

IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION, VOL. 17, NO. 2, APRIL 2001 125

Topological Simultaneous Localization and Mapping

(SLAM): Toward Exact Localization Without

Explicit Localization

Howie Choset, Member, IEEE, and Keiji Nagatani, Member, IEEE

Abstract—One of the critical components of mapping an

unknown environment is the robot’s ability to locate itself on

a partially explored map. This becomes challenging when the

robot experiences positioning error, does not have an external

positioning device, nor the luxury of engineered landmarks

placed in its free space. This paper presents a new method for

simultaneous localization and mapping that exploits the topology

of the robot’s free space to localize the robot on a partially

constructed map. The topology of the environment is encoded in

a topological map; the particular topological map used in this

paper is the generalized Voronoi graph (GVG), which also encodes

some metric information about the robot’s environment, as well.

In this paper, we present the low-level control laws that generate

the GVG edges and nodes, thereby allowing for exploration of

an unknown space. With these prescribed control laws, the GVG

(or other topological map) can be viewed as an arbitrator for a

hybrid control system that determines when to invoke a particular

low-level controller from a set of controllers all working toward

the high-level capability of mobile robot exploration. The main

contribution, however, is using the graph structure of the GVG,

via a graph matching process, to localize the robot. Experimental

results verify the described work.

Index Terms—Exploration, localization, mapping, mobile

robots, motion planning, tologoical maps, Voronoi diagrams.

I. INTRODUCTION

ENSOR-BASED exploration enables a robot to explore an

unknownenvironment and build a map of that environment.

A critical component of this task is the robot’s ability to ascer-

tain its location in the partially explored map or to determine

that it has entered new territory. Naively, one can determine the

coordinates of the robot using dead-reckoning, a process

that determines the robot’s location by integrating data from

wheel encoders that count the number of wheel rotations (or

fractional rotations). Dead-reckoning fails to accurately posi-

tion the robot for many reasons, including wheel slippage. If

Manuscript received January 4, 2000; revised October 23, 2000. This paper

was recommended for publication by Associate Editor L. Kavraki and Editor

A. De Luca upon evaluation of the reviewers’ comments. This work was sup-

ported by T. McMullen at ONR under Grant 97PR06977 and H. Moraff, J. Xiao,

L. Reeker, and E. P. Glinert at NSF under Grant IRI-9702768. This paper was

presented in part at the International Conference on Robotics and Automation,

Leuven, Belgium, 1998.

H. Choset is with the Department of Mechanical Engineering and

Robotics, Carnegie Mellon University, Pittsburgh, PA 15213 USA (e-mail:

choset@cs.cmu.edu).

K. Nagatani was with the Department of Mechanical Engineering and

Robotics, Carnegie Mellon University, Pittsburgh, PA 15213 USA. He is

now with the Man–Machine System Laboratory, Department of System

Engineering, Okayama University, Okayama 700-8530, Japan.

Publisher Item Identifier S 1042-296X(01)05570-7.

Fig. 1. The GVG where the symbols (nodes) are labeled 1–10.

the robot slips, the wheel rotation does not correspond to the

robot’s motion and thus encoder data, which reflect the state

of the wheel rotation, does not reflect the robot’s net motion,

thereby causing positioning error. A global positioning systems

(GPS) and inertial systems offer an alternative to dead-reck-

oning, but have their drawbacks as well. Finally, landmarks with

known locations can be deployed in the environment, but the

task described in this paper considers environments where their

geometry is completely unknown a priori. We do assume, how-

ever, that the unknown environment is static, planar, and that our

range sensors have sufficient range.

All robots that do not use preplaced landmarks or GPS must

employ a localization algorithm while mapping an unknown

space, hence the term simultaneous localization and mapping,

first coined by Leonard and Durrant-Whyte [16], [25]. This

paper takes a topological approach to SLAM. It is our belief

that the topological and geometric structure of free space induce

a natural hierarchy of symbols and connections among these

symbols that represent free space. At a high level, a topological

map [14] serves as an example of symbols and connections

between them. For Kuipers, the symbols are distinct places,

which are local maxima of the distance to nearby obstacles,

and the connections are the graph edges that link distinct

places. For an indoor office-like environments, junctions and

termination points of hallways represent symbols while the

hallways themselves are the connections. For the generalized

Voronoi graph (GVG) [21]; [7] (defined in Section II-A), the

Voronoi vertices (we call them meet points) are the symbols

while the edges form connections (Fig. 1).

126 IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION, VOL. 17, NO. 2, APRIL 2001

The connections of a high level representation can be dis-

cretized into a sequence of symbols with their corresponding

set of connections. Leonard and Durrant-Whyte’s approach to

SLAM is an excellent example [16], [25]. Their method uses

sensor information to define “features” and the relation among

them to direct a robot experiencing positioning error. Using a

Kalman filter approach to determine the “best” correlation of

features, the robot navigates similarly to a sailor using stars to

navigate a ship at night. Through the proper understanding of

the robot’s relationship to the features, the robot can maintain

an accurate estimate of its position while moving through the

environment using the features as low-level symbols that guide

the robot from one high-level symbol to the next.

At a low level, the robot’s environment can be modeled by

a local map such as a fine array of pixels [20]; [12]. Thrun

et al. [27] have been incredibly successful in demonstrating

their probabilistic approach in museum environments using

a grid-map representation. It is the belief of the authors that

Thrun’s main contribution is how to process a local map,

whether it be topological or a grid, not the local map itself.

Our contribution presented in this paper is to reduce the SLAM

problem to a graph matching problem at the topological scale,

not the graph matching itself.

Finally, defining the symbols and their connections is not

enough. Stable well-defined control laws must ensure that the

robot can identify (and converge onto if necessary) a symbol lo-

cation while at the same time move from symbol to symbol, i.e.,

traverse an edge. Although the philosophy of this work is gen-

eral to other topological maps, the map used in this paper is the

GVG, which is a map embedded in robot’s free space and cap-

tures the topologically salient features of the free space. With

the GVG the robot can plan a path between any two points in a

static environment by first planning a path onto the GVG, then

along the GVG, and finally from the GVG to the goal. Thus,

knowing the GVG is equivalent to knowing the free space and

constructing the GVG is akin to exploring the free space.

The GVG can be defined in an arbitrarily dimensioned Eu-

clidean space, but this paper stresses the planar version. We

present in this paper well-defined control laws that generate

GVGedges using line-of-sight range data. In deriving these con-

trol laws, we assume that the range and azimuth resolution of

the sensors are adequate to capture the structure of the robot’s

environment. Finally, we are assuming that the obstacles in our

environment are planar extrusions into three-dimensions, i.e.,

the obstacles are at the correct height for the sensors. With the

control laws, the GVG is not only a representation of free space

but it also forms a basis for exploring free space.

This paper presents some experimental results on how the

robot can incrementally construct the GVG in an unknown

space. Critical to this task is the robot’s ability to locate itself

on a partially constructed GVG. Although the robot locates

itself (topologically) on the GVG, it never needs to determine

its

coordinates (hence, the title of this paper). The robot

can propagate the coordinates of each point on the GVG from

the known location of one point, such as the start point, which

can be specified to be

In this paper, we first refer to prior work which has influenced

the authors’ thinking. Then, we define the GVG and prescribe

the control laws to construct it. Incrementally constructing the

GVG is not enough because of dead-reckoning error, as will be

shown by example. We then introduce a the following three-

tiered approach to localization: zero dimensional (using sensor

signatures of the nodes); one dimensional (intentionally fol-

lowing a sequence of edges to a desired node); and two di-

mensional (handling the situation where the robot accidentally

re-encounters an already-visited node). Finally, we discuss the

tradeoffs of this approach and future work.

II. R

ELATION TO PRIOR WORK

This work draws from two areas: sensor-based planning and

localization. Although both of these fields are vast, we only dis-

cuss papers that have influenced our thinking.

A. Sensor-Based Planning and Roadmaps

Much of the previous work in sensor-based planning is

heuristic and is limited to the plane. One class of heuristic

algorithms employs a behavior-based approach in which the

robot is armed with a simple set of behaviors (e.g., following

a wall) [4]. Another heuristic approach involves discretizing

a planar world into pixels of some resolution. Typically, this

approach handles errors in sonar sensing readings quite well

by assigning each pixel a value indicating the likelihood

that it overlaps an obstacle [20]; [2]. Many heuristics exist

for planning with the discretized map. Many behavior-based

heuristics are sometimes termed as reactive control in that low

level inputs directly affect the high level behavioral outcomes

for the robot. Strong experimental results indicate the utility

of these approaches, and thus these algorithms may provide a

future basis for complete sensor-based planners. Unfortunately,

these approaches currently neither afford proofs of correctness

that guarantee a path can be found, nor offer well-established

thresholds for when these heuristic algorithms fail. One of

the goals of the work presented here is to demonstrate how

low level inputs can direct a robot to construct a high-level

representation: a topological map.

We seek to adapt the structure of a provably correct classical

motion planning scheme to a sensor-based implementation.

For example, Lumelsky’s “bug” algorithm [19] proves that a

robot using on-line information can plan a path to the goal.

This method, however, does not yield a map of an unknown

space. Our approach is based on a roadmap [5], a one-dimen-

sional subset of a robot’s free space, which captures all of its

important topological properties. A roadmap has the following

properties: accessibility; connectivity; and departability. These

properties imply that the planner can construct a path between

any two points in a connected component of the robot’s free

space by first finding a path onto the roadmap (accessibility),

traversing the roadmap to the vicinity of the goal (connectivity),

and then constructing a path from the roadmap to the goal

(departability). If the robot can incrementally construct the

roadmap, then it has in essence explored its free space because

the robot can always use the roadmap to plan future excursions

into the free space.

Already, the motion planning field has produced many

roadmaps: silhouette methods [5], Voronoi diagrams [21],

CHOSET AND NAGATANI: TOPOLOGICAL SLAM: TOWARDS EXACT LOCALIZATION WITHOUT EXPLICIT LOCALIZATION 127

visibility graphs [15], etc. (see [15] for a survey of roadmaps).

The roadmap used in this work is the GVG [7], which is the

one-dimensional set of points equidistant to

obstacles in

dimensions. In the plane, the GVG is simply the generalized

Voronoi diagram, which is the set of points equidistant to two

obstacles [21]. In a three-dimensional Euclidean space

, the

GVG is the one-dimensional set of points equidistant to three

obstacles.

Rao [22] achieves exploration by incrementally constructing

the planar GVG in a two-dimensional static polygonal envi-

ronment. Choset and Burdick [6] also describe a method to

construct the GVG in a static

-dimensional environment, but

their approach does not require obstacles to be polygonal, poly-

hedral, nor convex, which are assumptions most motion plan-

ners require. Both methods assume that the robot only uses

line-of-sight information.

Both Rao’s and Choset and Burdick’s methods also assume

that the robot is equipped with a 360

field-of-view high az-

imuth infinite range sensor that detects nearby obstacles. They

do not consider how real range readings can be integrated into

a control law to direct a mobile robot. In this paper, we present

control laws that take low level sensor information and then di-

rects the robot to follow the GVG edges without knowing the

GVG ahead of time. This has the affect of incrementally con-

structing the GVG. Here, low level reactive-style control has a

direct affect on high level behavior of the robot which guaran-

tees that the robot explores an unknown space. This control law

works well in small environments with a mobile robot equipped

with a ring of sonar sensors [9]. Unfortunately the control laws,

by themselves, are not enough for deploying a robot in large

environments because of errors in encoder readings. The main

contribution of this paper is to use the topology encoded in the

GVG to overcome these errors and to localize the robot.

B. Localization

Localization is a major area of mobile robotics that has

received increased attention over the past decade. Again, the

literature in this field is vast, so only work which has influenced

this paper’s results are mentioned. See [3] for a complete

overview of current localization techniques. Lu et al. [17], [18],

[13] use gradient ascent to update various location estimates

forward and backward in time. As a result, this approach has

led to significantly larger maps that are more accurate than

previous approaches, but is still limited to situations with

bounded odometric error. Shatkay and Kaelbling [24] proposed

an approach that uses probabilistic representations, along

with the well-known Baum–Welch algorithm for efficient

estimation. Their approach is similar in nature to the one

described by Thrun [27], in that they both employ probabilistic

representations and both use the Baum–Welch algorithm.

However, the method in [24] does not consider orientation

dead-reckoning error.

Thrun has recently completed a localization approach that

has been successfully verified in very large environments on

a mobile robot where a map is known a priori or the robot

is driven (currently by an external agent) to acquire environ-

mental information [27]. This approach poses a maximum-like-

lihood estimation problem, where both the location of land-

marks and the robot’s position have to be estimated. Likelihood

is maximized under probabilistic constraints that arise from the

physics of robot motion and perception. Just like [27], they use

a Baum–Welch (or alpha–beta) algorithm. Unfortunately, this

approach requires a user to specify the landmarks, as opposed

to the robot self-selecting them. Also, their approach does not

include an exploration strategy. In other words, there is nothing

in their approach that directs the robot to explore new areas, or

that guides the robot to specific locations to reduce dead-reck-

oning error.

C. Localization with Topological Maps

The above localization techniques took the approach of con-

stantly trying to update the robot’s

coordinates relative

to a global frame. In this paper, we localize the robot on a topo-

logical map without ever having to do so explicitly. Others such

as Dudek [11] and Kuipers [14] have reported localization re-

sults with the same philosophy. In [11], an agent locates itself

on a graph by matching nodes and the adjacency relationships

between them. This approach assumes that the agent can label

each node by depositing a marker at the nodes. The approach in

this paper and in [14] has the robot automatically identify nodes

in the topological graph from geometric environmental infor-

mation.

The basic thrust of this paper’s work is quite similar to

Kuiper’s. In [14], the robot essentially traces points that are

equidistant from two portions of the environment until it

reaches a point that is three-way equidistant or until it reaches a

point where a distance threshold is met, at which point the robot

follows the obstacle boundaries. The nodes in this graph are

termed distinct places, which are local maxima of the distance

to nearby obstacles. The robot can easily self-determine distinct

places from sensor data. Distinct places are a subset of the

nodes of the GVG, which are the set of points equidistant

to three obstacles (in other words, there exist examples of

triple equidistance that are not local maxima). Localization is

achieved again by matching distinct places of the graph.

D. Simultaneous Localization and Mapping (SLAM)

Leonard and Durrant-Whyte coined the term SLAM, which

as its name suggests, enables a robot to construct a map of an

unknown environment while using the same map to bound or

nullify positioning errors [16]. With SLAM, the robot must au-

tomatically determine landmarks while constructing the map.

Smith and Leonard [25] developed a feature-based approach to

address SLAM by generating multiple hypothesis and selecting

among them while mapping an unknown region. The work pre-

sented here builds upon Leonard and Durrant-Whyte’s work by

determining a rigorously well-posed method for identifying fea-

tures and the topological relations among them.

Schultz et al. [23] present a more conventional approach to

SLAM that uses certainty grids. This approach is more of an

outgrowthof the algorithms presented in Section II-B. Although

this work does not directly impact the SLAM algorithm pre-

sented in this paper, Schultz and our approaches share some

common ideas and problems.

剩余12页未读，继续阅读

评论收藏

内容反馈

jpthank

粉丝: 1
资源: 12

5.Topological simultaneous localization and mapping (SLAM) towar...

评论0

最新资源

5.Topological simultaneous localization and mapping (SLAM) towar...

评论0

A Survey of Simultaneous Localization and Mapping(2).pdf

GTM003.Topological.Vector.Spaces.-Helmut.H..Schaefer.djvu

GTM003.Topological.Vector.Spaces.-Helmut.H..Schaefer (1).pdf

topology__2Ed_-_James_Munkres.pdf

GTM002.Measure.and.Category（测度和范畴：一份关于拓扑空间和测度空间类似的概要）

Java实现-Topological Graphing

【Lintcode】127. Topological Sorting

Weak Anti-Localization and Quantum Oscillations in Topological Crystalline Insulator PbTe

GTM 003 Topological vector spaces - Schaefer H.H. (GTM003 1ed. Springer 1971)(ISBN 0387053808)(K)(600dpi)(T)(307s)_MCf_

基于多机器人协作的未知环境下路径探索研究

introduction to topology pdf 高清 书签

Topological Spaces: Including a Treatment of Multi-Valued Functions, Vector Spaces and Convexity

introduction to topology

Springer Press：Triangulations and Applications

Skiena-The_Algorithm_Design_Manual.pdf

deep_learning apply in Quantum physics

Nexus and Dirac lines in topological materials

Topological and Statistical Methods for Complex Data

Topological Algorithms for Digital Image Processing Machine Intelligence and Pattern Recognition

Java第十五届蓝桥杯大赛软件JavaB组真题

SwitchHosts

安卓期末大作业（AndroidStudio开发），垃圾分类助手app，分为前台后台，代码有注释，均能正常运行

Notepad++安装包

2024北森能力测评题库.7z

微信小程序源码-合集1.rar

Java面试八股文2023最新版

Linux Centos7 升级最新版OpenSSH-9.6p1 有脚本（支持离线）

JDK1.8 windows 64位

ruoyi-vue-pro 芋道源码项目的表结构

最新资源

introduction to topology pdf 高清书签