A pathfinding algorithm for a myopic robot

^^^^^^^^^1 A U T I C S

A Pathfinding Algorithm for a

2

&JSa»J3 2££

^£

(PAGES)

S (NASA CR OR TMX OR AD NUMBER)

IMBER)

J ET

V> M L i

11

GPO PRICE $

CSFTI PRICE(S) $

Hard copy (HC)
Microfiche (MF)

ff653 July 65

3*&*D

c 63'

(THRU)

(CODE)

£1

(CATEGORY)

* 1 1 fj § 1 1 1 a ■ lilllll 1 1 1 1 ft 1

■lllil

liSiii spin

• til

llilBiilllr V W

NATIONAL AERONAUTICS AND SPACE ADMINISTRATION

Technical Report 32-1288

A Path finding Algorithm for a Myopic Robot

Larry Y. Urn

Approved by

&S5*

W. F. Scott, Manager

Flight Computers and Sequencers Section

J i T PRO P U L S I O N LABORATO R Y

CALIFORNIA INSTITUTE OF TECHNOLOGY
PASADENA, CALIFORNIA

August 1, 1968

TECHNICAL REPORT 32-1288

Copyright © 1968

Jet Propulsion Laboratory

California Institute of Technology

Prepared Under Contract No. NAS 7-1 00
National Aeronautics & Space Administration

Acknowledgment

The author wishes to thank W. F. Scott and J. J. Wedel for providing the
opportunity to work on the pathfinding problem. Stimulating discussions with
Dr. C, L. Lawson, Dr. G. Paine, D. Rennels, J. Rohr, E. Suggs, W. Garrison, and
C. Carl are acknowledged by the author. P. Sobel provided the computer program
used to generate the perspective drawing of contour configurations. In addition, the
guidance provided by J. J. Wedel and D. K. Rubin is gratefully acknowledged.

JPL TECHNICAL REPORT 32-1288 Hi

Page intentionally left blank

^SCEDIRG P AGE BEAEfK HOT

fllfflED,

Contents

I. HIIIUUUVHUII .......

11. Mathematical Development

A. Proposition 1 ......

B. Proposition 2

III. The Pathfinding Algorithm . .

A. Main Algorithm ......

B. Right Scan Algorithm ......

C Simulation of Topography . .
D. Computer Program for the Pathfin

IV. Conclusion ..........

References ..

ding Algorithm and Results .

2
2
3

4
4
5
5
6

6

20

Figures

1 . Box canyon problem

2. Confour configuration constrvcfed by use of Gaussian hills . .

3. Perspective drawing of contour configuration .. . . ., . . .

4. A maze constructed by use of Gaussian density functions . . .

5. Graph for calculating and constructing any configuration required
for the simulation of terrains ,

6. Flow chart of computer program, main algorithm , .. . . : . .

7. Flow chart of computer program, left scan algorithm . . . .

8. Flow chart of computer program, right scan algorithm ....

9. A simple obstacle course of five Gaussian hills . , . . . . .

10. A simple box canyon configuration

] 1 . A maze in which the starting point is outside of the maze and
the target point is inside .

12. Same maze in which the starting point is inside the maze and the
target point is outside . .

13. Result of the robot crawling on and over hills .......

4
7
8
9

10
11
13
14
15
16

17

18
19

JPL TECHNICAL REPORT 32-I28B

Abstract

A pathfinding algorithm has been developed for an autonomous myopic roving
vehicle. With the assumption that a path exists between two points, two proposi-
tions are proved. Proposition 1 is concerned with no obstacles and proposition 2
is concerned with at least one obstacle. Various conditions are established and
terms defined. Three algorithms, necessary to direct the robot, are main, left scan,
and right scan. The decisions for the navigation, control, and obstacle avoidance
of the rover are based mainly on myopic (local) information of the terrain. The
use of Gaussian density functions to simulate topography is considered to be
novel A FORTRAN IV computer program was written to implement the path-
finding algorithm, and the results of the computer-program runs were satisfactory.

vi JPL TECHNICAL REPORT 32-1288

A Pathfinding Algorithm for a Myopic Robot

I. Introduction

It has been more than ten years since E. F. Moore
published his article on pathfinding algorithms (Ref. 1).
In 1961, C, Y. Lee published his paper on an algorithm
for path connections (Ref. 2). The algorithms discussed
in the two references have three basic assumptions in
common: (I) the map is completely known, (2) each path
can be retraced, and (3) an optimum path can be deter-
mined. The question arises as to what degree of a priori
information about the map must be known in order to
determine a path from one point to another point such
that it will satisfy a given set of constraints. Here, one
may not be interested in obtaining the shortest path, but
rather a safe path from one point to another point (i.e., if
such a path exists). The impetus for the above question
stems from the application of pathfinding algorithms to
unmanned planetary exploration, such as the navigation
and control of an autonomous roving vehicle on the sur-
face of Mars to explore its topography. It is assumed that
various orbital reconnaissances, similar to that of the
Lunar Orbiter, have been performed and a gross knowl-
edge of the topography of the planet is available. Conse-

quently, the landing site and the various interesting
target areas to be visited can be determined.

The transmission of the orbital reconnaissance infor-
mation from a distant planet may take many weeks to
accomplish because of limited transmitter power. Be-
cause of this limitation, if one is to land a roving vehicle
on a distant planet, the continuous direct control of the
vehicle from earth, as in the case of the Surveyor, will
be extremely time-consuming and will probably prove
to be infeasible. Consider the case of the Mariner Mars
1964 mission. Each television picture consisted of a
200- X 200-element matrix in which each element con-
sisted of six bits. Since the transmission data rate was
8-1/3 bits/s, it took eight hours to assemble one tele-
vision picture. Furthermore, direct control from earth of
the vehicles' motion on distant planets will be extremely
difficult because of transport lag in the control loop
(Ref, 3). This makes the use of direct control of the
vehicle from earth prohibitive. Therefore, the roving ve-
hicle should be autonomous, with minimal command
requirements for control of motion from earth.

JPL TECHNICAL REPORT 32-1288

1

It is the purpose of this report to discuss the results of
a study involving a pathfinding algorithm for an autono-
mous roving vehicle. The algorithm requires only infor-
mation that is within the field-of-view of die vehicle
(i.e., local information). Essentially, the study involves
designing a pathfinding algorithm for a myopic robot,
the requirements of which are as follows:

(1) The robot shall see the terrain that is within its
scanning range.

(2) Any obstacles within the robot's scanning range
may be sensed.

(3) The initial starting coordinates (the landing point)
shall be given.

(4) The target coordinates to be visited shall be given.

(5) If a path exists, the algorithm shall find the path.

(6) The algorithm shall avoid hazardous obstacles and
be able to crawl on and over safe obstacles.

(7) The algorithm shall use a minimal number of
memory locations for the navigational path.

11. Mathematical Development

The pathfinding algorithms developed in this report
are based upon two propositions:

(1) If a path exists from the point P , (X , Y ), to the
point P n , (X», Y»), and there are no obstacles be-
tween the two points, then the path connecting
these two points can be found,

(2) If a path exists from the Point P , (X , Y ), to the
point P n , :(X», Y„), and at least one obstacle exists
between the two points, then following either the
right or left contour of the obstacle and always
heading toward the target point P n will result in
determining a path between P and P n .

The above propositions assume that the obstacles have
contour lines and that each obstacle has finite dimension
.(le., no infinitely thin obstacles). The proof of the above
two propositions is based on whether a target distance
sequence contains an element that can be made arbi-
trarily small or not. If such an element exists, then the
target point is reached. Otherwise, the algorithm, which
makes use of the above propositions, will result in limit-
cycle oscillation.

Definition 1. An acceptable point is defined as a point
(X,Y) such that |F(X,Y) j < E, where F(X 3 Y) is a contin-

uous function that describes the terrain and E is the
elevation limit.

Definition 2. A path is defined as a route that connects
two points (Xi,Y.i) and (X 7 - 5 Y ; -) such that the elevation of
each point of the route is jF(X,Y) | < E.

Definition 3. An obstacle is defined as a finite bounded
region of a function whose amplitude or values are
greater than E, where |F(X,Y)| > E. \

A. Proposition I

If there exists a path from the point P , (X 0? Yo), to the i
point P w , (X„,Y n ), and there are no obstacles between
the points P and P w , then the path can be found by the
algorithm.

Proof:

Let the first intermediate point of travel be (X 1? Yi)
such that

X x = X + r*cos<9!

Yx = Y ■■+ r*smB t

where r is a fixed distance increment (scanning range)
and

9 1 = tan

\X n — Xo/

In general,

X i+1 s= Xi + r*cos^ i+1
Y i+1 = Yi 4* r*sin^ i+1

where

i+i = tan

\ X n *— Xi /

Since there are no obstacles between P and P n , then
every point on the line P Q P n is an acceptable point
and 6i == 6 X for all L

Let the target distance sequence be {d u d 2 , ■• • • , d n }

4 = l(X n - X^) 2 + (Y, - Y^TV^

By proper choice of r, the final d% can be made as
small as one quantized r (Le., d^ < r). Hence, the tar-
get is reached.

JPL TECHNICAL REPORT 32-1288

Proposition 1 essentially states that, if the starting
point (X ,Y o ) and the target point (X„,Y„) have the prop-
erty that |.F(Xo,Yo) | < £ and \F(X ny Y n ) | < E, and there
are no obstacles between these two points |F(X,Y)| < E
for all (x,y) between these two points, then we ean de-
termine a path that connects these points. The idea of
proposition 1 is rather obvious. However, the introduc-
tion and use of the target distance sequence in proving
proposition 1 is the main reason for the detailed proof.
Proposition 2 will also make use of the target distance
sequence argument.

B. Proposition 2

If a path exists from the point P , (X ,Y ), to the point
P w , (X„,Y n )> and at least one obstacle exists between the
two points, then following either the right or left con-
tour of the obstacle and always heading toward the tar-
get, P n , will result in determining a path P P n *

Proof;

This proposition will be proven by the use of mathe-
matical induction. It will be shown that the proposi-
tion is true for one obstacle between P and P„. If it
is assumed to be true for m obstacles, then it can be
shown to be true for m 4- 1 obstacles between P and
P w . Let the one obstacle between P and P n have the
contour represented by F(X,Y), Let the first point of
travel from (X ,Y ) to (Xi,Yi) be P 1? such that

X x = X + r^cos$ 1

Y t = Y + r*sm$ %

where r (the scanning range) is the distance increment,

and^^tan-^^-— -)

The point (X ,Y ) has a neighborhood that eontaius
some acceptable points, because the assumption of a
path exists between the points P and P n . Let the
acceptable contour elevation limits be given as E.
Evaluate F(X 1 ,Y 1 ). If \F(X 1 ,Y 1 )\ < E, then (X l9 Y ± ) is
an acceptable point. Now replace (X ,Y ) by (X^Ya),
then proceed to evaluate (X;,Yi) for i = 2, 3, • • • , etc.
However, if \F(X 1 J 1 ) | > E, replace 6 t by t ±A0. If
X + AO is used in determining (X l5 Y x ), the left con-
tour is being followed. If 6 X - AO is used, then the
right contour is being followed. Evaluate the new
F(X 1 ,Y 1 ) by varying AO, until an acceptable point is

determined. Also, determine the distance from (X^Yt)
to (XnJn) i.e.,

rf i 2 =(X 7l -X 1 ) 2 + (Y ft -Y 1 ) 2
The angular increment and decrement in AO is 1 deg.

The scanning process is continued until a first ac-
ceptable point is found. This point also determines
whether the right or left contour is to be followed.
The crawling process is repeated and a target dis-
tance sequence {d x , d 2 , '• ■• • , d%}, is generated until
an acceptable point (X ft ,Yfc) such that

di > 4 +1 = [(X n - X,) 2 + (Y n - Y*) 2 ] *'*

is satisfied. Term d$ was the minimal distance from
the target to (X h Yj), the point where the obstacle was
first encountered and k > jf. From the point (Xfc,Y fe )
to (X„,Y»), we can apply proposition 1. If the target
has not been reached after the use of proposition 1,
the above scanning is repeated until the target is
reached. Therefore, proposition 2 is true for one
obstacle.

Assume that proposition 2 is true for m obstacles.
We will have to prove that the proposition is also true
for m + 1 obstacles. Let the intermediate point of
travel from (Xi,Yi) to (Xi+i,Yi+.i) be P i+1 , such that

X i+1 == Xi + f*cas0 4+ i

Y Ut = Y i + r*sfo0, +1

0$*i == tan~

\ X n — Xi /

The expression Xi,Y* is the point where It departed
from obstacle m and encountered the m + 1 th obstacle.
Term di is the minimal distance from the target to
.(Xi,Yi). Let the acceptable contour elevation limit be
the same as before, E. Evaluate F(Xi + i,Y i+1 ). If
|F(X i+1 ,Y i+1 )| < E, then .(Xi +1 ,Y i+1 ) is an acceptable
point. Now replace (X h Yi) by (X i+1 ,Yi + i). Then, pro-
ceed to evaluate (Xi +2 ,Yi +2 ), etc. However, if
|F(X i+1 ,Y i+1 )| > E> replace $ Ul by $ M dr AO. Eval-
uate the new |F{Xi +1 ,Y i+1 )| until an acceptable point
is determined. Also, determine whether d i+1 < di, i.e.,

(X w -X i+1 ) 2 + (Y w -Y u *) 2 < (Xn-XO 2 + {Yn-Ytf

JPL TECHNICAL REPORT 32-1288

If after some P iterations, d p < di, and there are no
obstacles between P v and P n , we can apply propo-
sition 1. In general, there is a monotonic decreasing
subsequence of {di,<2 2? * • \d n % say {dmud^z,* • • A«} 5
where each dm% is a local miirtaum distance to the
target such that dmi +1 < dmi for all i. Hence, the tar-
get is reached. Therefore, proposition 2 is true for
m + 1 obstacles.

The proof of proposition 2 can be simplified by use of
inductive argument on each obstacle grossly, ratitier than
point by point. Any obstacles that merge together can be
considered as a single obstacle. The value of the target
distance sequence element controls the use of either
proposition 1 or proposition 2. Consider the case of a
box canyon. Let <i& be the distance from the end of
the box canyon (Fig. 1) to the target. Assume that the
right contour is being followed. Then all target distance
sequence elements <4+i> dh+ 2 , •*•, generated will be
greater than d k . Thus, the right contour is being followed
until a dm < djc is found and proposition 1 is applied.
Then, <4 is replaced by d^. This iteration process is con-
tinued until the target is reached.

d . = d v , < d. = d.
mm 1] 1 k

Fig. 1. Box canyon problem

Hi. The Pathfinding Algorithm

The pathfinding algorithm consists of three algorithms,
which are called main algorithm, left scan algorithm, and
right scan algorithm. The main algorithm directs the
robot to move either straight ahead, in the right direc-
tion, or in the left direction. The left scan algorithm
directs the robot to move in the left direction only. The
right scan algorithm can only direct the robot to go to
the right. The right and left scan algorithms enable the
robot to navigate out of box canyons.

A. Main Algorithm

The main algorithm can be described by the following
steps:

(1) Construct a vector, called target vector, by using
the starting point (X ,Y ) and the target point

(2) Determine the azimuth of the target vector and
call it 8.

(3) Let the next point of travel be (x,y) such that

x = X + r*cos& ^

y == Y 4- r*sin#

where r is the maximum scanning range of the
robot and is defined the same as step (2).

(4) Evaluate the contour map F(x,y) at the next point
of travel (x,y). If \F(x,y) \ is within a prescribed
contour limit, i.e., J F(x,y) | < E is defined as the
elevation limit (Definition 1), go to step (6); if not,
goto step (5).

(5) Start scanning by varying the azimuth in incre-
ments of 1 deg (i.e., ± 1 deg) until an acceptable
contour limit is reached. The scanning process
scans 1 deg to the left of the azimuth, then 1 deg
to the right; 2 deg to the left, then 2 deg to the
right, etc. If at (x,y), F(x,y) has an acceptable con-
tour limit, go to step (6). If no such point exists,
go to step (8).

(6) Determine whether the target has been reached or
not. If the target has not been reached, replace
(X 6 ,Y&) with (Xo,Yo), where (X 6 ,Y&) is the previous
point. Also replace (X 03 Y ) with (x 9 y). If

x = X + r^cos^

y = Y + r*sin^

is an acceptable point, set the right counter,
CTR = 0.0, and the left counter CTL == 0.0. If
the point

x = X + r*cos (0 + AO)
y = Y + r*sin (6 + AS)
is an acceptable point, set CTR = 1.0 and compute

JPL TECHNICAL REPORT 32-1288

If the point

x = X + r*cos(0 ~ AS)

^ = Y G + r*sin($ - A0)

is an acceptable point, set CTL = 1.0 and compute

ZV= l(x t - x)* + (y t - y)*V /2

Go to step (7). If the target has been reached, the
job is finished. If both right and left counters are
not 1.0, go to step (I).

(7) If both counters are 1.0, the robot is trapped. If
the distance from the right point to the target is
shorter than the distance of the left point to the
target, go to the right scan algorithm. Otherwise,
go to the left scan algorithm.

(8) The robot is trapped. In this case, there exists no
path from point F to P t . Hence, there exist no ac-
ceptable points in the neighborhood of P Q . The
robot may have landed on the peak of a mountain.

B. Right Scan Algorithm

Because the left scan algorithm is similar to the right
scan algorithm, it is sufficient to describe the right scan
algorithm. In order to force the algorithm to crawl along
the contour edge, a crawling vector is defined. The right
scan algorithm can be described by the following steps:

(1) Construct a target vector using (X ,Y ) and (X tj Y t ),
Also construct a crawling vector using (X&,Y&) and
(X ,Y ). The minimal distance from (x 9 y) to (X t ,Y t )
at the time of encountering the obstacle is
Dmin = D t .

(2) Determine the azimuth of both the target vector
and the crawling vector. Call the crawling vec-
tor azimuth 01.

(3) Let the next point of travel be (x,y) such that

x = X + r*cos(0l + 90°)

y = Y + r*sin(0l 4- 90°)

where r is the maximum scanning range and 01 is
defined the same as step (2).

(4) Evaluate the contour map F(x,y) at (x,y). If
|F(x,t/)| at {x,y) is within the prescribed contour
limit, go to step (6); if not, decrement 01 by one
angular degree until an acceptable contour value

of F(x,y) is obtained, The maximum decrement is
270 deg. Once an acceptable (x,y) has been ob-
tained, go to step (5).

(5) Determine the distance from (X,Y) to (Xt,Y t ) and
call it Dt. Replace <X 6 ,Y 6 ) with (X 0) Y ); and, (X ,Y )
with {x y y). Then go to step (6).

(6) If Dmin < D t , go back to step (1). However, if
Dmin > Dt, go to step (7).

(7) Evaluate F(x,y). If | F(x,y)\ > E, go back to step (1).
However, if | F{x,y) \ < E, reset the left and right
counter to zero and return to the main algorithm.
The point (x,y) is

x — X 4- r*cos0
y = Y + r*sin0.

C. Simulation of Topography

In the course of developing an algorithm for the
myopic robot, the problem encountered of inputting data
to the algorithm (for computer simulation) was difficult
because the data had to meet requirement (2) stated
in Section I. Since the input data was to be topography,
the data should have various levels of contours. A novel
solution for simulation of terrain was made by using
Gaussian density functions. Using the Gaussian density-
functions, one can simulate almost all terrain simply by
summing a series of "Gaussian hills." The locations of
these Gaussian hills can be fixed by assigning the means,
/ia, and /%, the desired coordinates. The shapes of the
Gaussian hills can be controlled by varying the value of
the standard deviations, <j x and o y . The height of the
Gaussian hills can be varied by using an appropriate con-
stant (positive and negative) multiplier of the Gaussian
density function.

Since the use of a set of Gaussian hills to simulate
topography will result in a very smooth surface, the
approximated terrain will not represent an exact topog-
raphy. However, this technique is so simple to use, all
terrain considered in this report is made of Gaussian
hills. The Gaussian hill technique can also be used to
classify and sense obstacles by covering each obstacle
with a Gaussian hill. Figure 2 shows a contour config-
uration that can be constructed by using Gaussian hills.
Figure 3 is a perspective drawing of the contour config-
uration of Fig. 2. Figure 4 shows a maze constructed by
use of Gaussian density functions. Figure 5 enables one
to calculate and construct any configuration required for
the simulation of topography.

JPL TECHNICAL REPORT 32-1288

D. Computer Program for the Pathfinding Algorithm and
Results

A computer program was coded in FORTRAN IV
language as implemented in the IBM 7090/94 IBJOB
System. The flow charts for the pathfinding algorithms
are shown in Figs. 6-8. The computer program, which
plots the contour lines of the obstacle, was developed
by Dr. Charles L. Lawson (Ref. 4) of the Computation
and Analysis Section at Jet Propulsion Laboratory. The
pathfinding computer program was organized so that
the contour lines of the obstacle were plotted first, and
then the path from the starting point to the target was
plotted. Various configurations of obstacle courses were
made and the robot satisfactorily navigated through
each course.

Figure 9 shows a simple obstacle course of five
Gaussian hills. The path, which connects the starting
and target points, satisfies the contour elevation con-
straint of E == I (i.e., |F(x,t/)| < 1.0), The scanning
range r is set at 0,1 unit. This means that the robot will
see no further than 0.1 unit ahead.

Figure 10 shows a simple "box canyon" configuration.
In this case, there are two paths to the target point. The
path determined by the algorithm is certainly not the
shortest path. The shortest path was not chosen, because
the decision to go to the right scan program was based
on the minimum azimuth scanning angle to the right.
Also, the distance from the right scanned point to the
target point was shorter than the distance to the left
scanned point. Using local information only, there are
no methods by which one can determine the shortest
path between two points.

Figure 11 shows a maze in which the starting point is
outside of the maze and the target point is inside of the
maze. Figure 12 shows the same maze as Fig. 11; how-
ever, the starting point is inside the maze and the target
point is outside of the maze. In all cases which were run
on the computer, paths were found for each case,

IV. Conclusion

This report has demonstrated that it is possible to find *
a path connecting two points on a continuous contour
map, using only local information. The algorithm used
to find a path is based on two propositions. In turn, these ^
propositions were based on intuitive ideas that are used
in unknown areas. One of the assumptions used in prov-
ing the propositions was that there exists at least one
path from the starting point to the target point. This is
not an unreasonable assumption. If one were to land a
spacecraft inside a crater and the wall of the crater was
very steep, such that the vehicle could not extricate itself
from the crater, one would have to terminate the mission.

The algorithm developed in this report might be im-
proved by incorporating certain local terrain informa-
tion, such as the hidden lines of obstacles (Ref. 5). The
slopes of local areas can also be incorporated so that
the vehicle will have minimal tilt angles while it travels
from one point to another point. Furthermore, if we de-
fine a subpath as \f(%i$i) — /(£*-i,J/»-i).] < £ for all I's
and for a distance of r, then the algorithm will allow
the robot to crawl on and over hills. Figure 13 shows the
result of the robot crawling on and over hills.

The present scanning portion of the computer program
is based on simple strategy. Future work will incorporate
the scanning strategy of ranging radar.

JPL TECHNICAL REPORT 32rl28B

3,oaa

*

■*

illlilli

: $4$.&,

Fig. 2. Contour configuration constructed by use of Gaussian hills

JPL TECHNICAL REPORT 32-1288

Fig. 3. Perspective drawing of contour configuration

JPL TECHNICAL REPORT 32-1288

s.aoai

«m$

*$.i$M. ■■ *4. t *m. : ■*»:*>#»■ . .-$..» . ^ -!,s*»;

! $01 I « -\*80 *.C

Fig. 4. A maze constructed by use of Gaussian density functions

JPL TECHNICAL REPORT 32-1288

i<r

10

10

/ A

/ ^2

*(x)

= -{Ax/a- )
Ax

k

~ cr

\

\

,o" 3

0.4 0.8 1.2 1.6 2.0 2.4 2.8

k

Fig. 5. Graph for calculating and constructing any
configuration required for the simulation of terrains

10

JPL TECHNICAL REPORT 32-1288

r^

en

<

w

I—

o

o

6

>

^

UJ

t-

Q

o

>

o£ _

X

».

on ,

t—

— li

l/>

X

uj co

1—

T

LO

2uT .

O

1—

z

S <£u

o_

o

IS

o

OZ!5

C!)
Z

ANNIN
EVATIO

OSURE

*^

<

V _J r-J

CO L1J D

LO

H-

CM

^

CM

O

>

i—

^>^

UJ

H-

3

+

CM

o

O

X

1—

X

11

z

^

Q

CD

oo

o

U

m

*

h-

oc

a.

+

^

o

o

X

u

11

X

JtooouE mum f

JPL TECHNICAL REPORT 32-7288

o

.

o

U
t—

O

QZ

h-

t—

aa

7

1—

< )

Z

H-

u

O

1—

U-

LJJ

i

an

I—

J—

LU

LU

co

CO

U

X

>

<

__j

o

o

CL,

LU

X

>

^-s

cd q>

< <

a> <d

LU

" >— -

1—
CL.

-co _

o z

£

U co
* *

o

C£ ££

u

+

+

o o

X

>-

11

If

X

>

■Q

LU

CO

1—

LU

CO

_l

o

— 1

o

<J

T

I

£

S

cm

>-

1

2<^

LU \
VI \

_i
Q

^

a>

CD

<

<

+

+

CD

CD

LU

>— '

*»— "

.f—

CO

CL.

o

z

2

CO

*

o

D£

Ctl

u

+

+

o

o

X

>

ii

1!

X

>-

VI

co >i

£

<

Q£

LU O

■m

o Q -

ol

pp

*- z

zl

o<

>< CO

tz

LU

££ ^

a

f(p«>OT JEfflffl o

o
JP

c

"5

E

£
o

I

a.

D

a.

E
o

u

**-
O

t

11

Page intentionally left blank

PRECEDING PAGE BLAHK

not w&Sb.

f LEFT SCAN "\
V ^ PROGRAM J

COMPUTE
CRAWLING VECTOR

Q\ AND 9
6} = TAN"

•1 f Y b~ Y

V X

8= TAN

-1 , Y T- Y

x T -x c

COMPUTE
x = X G + R*COS (01 + 9.0 -A3)

y = Y + R*S|N (01 + 9O-A0)

NO

COMPUTE

D t=V( x t- x f + f y t- y V

SET AG = A0 + 1°

YES

REPLACE
DMIN BY D,

REPLACE

x b

8YX ANDX

BY x

Y b

BY Y Q AND Y Q

BYy

NO

NO

Fig. 7. Flow chart of computer program, left scan algorithm

JPL TECHNICAL REPORT 32-1288

13

RIGHT SCAN
PROGRAM

REPLACE:
DM IN BY D

COMPUTE
CRAWLING VECTOR

01 AND

01 = TAN

= TAN

■lf Y b" Y
X b~ X

\V X 0J

COMPUTE
x = X + R*COS (01 - 90 +A0)

y == Y +R*SIN (01 -90+ AG)

YES

NO

i

SET A.6 = AS +1°

COMPUTE

3 t = V( x t" x ) 2 + ( y t" yX2

T

REPLACE
X b by X Q AND X Q BY x

Y L BYY^AND Y n BY y
b '

YES

NO

YES

£

NO

Fig. 8. Flow chart of computer program, right scan algorithm

14

JPL TECHNICAL REPORT 32-1288

;!.*«■■ ''■ ■;.':*v0Oij ' ' . :t,*Hfl»

Fig. 9. A simple obstacle course of five Gaussian hills

JPL TECHNICAL REPORT 32-1288

15

5,000

Fig. 10. A simple box canyon configuration

16

JPL TECHNICAL REPORT 32-1288

4.0^0 f~..

5,000 i..

a.aoo 4*..,

t.oaa 4>-

-1*00© *-..

-ff.0O8 #~

-9,000' *■■

STARTING
~4,&m &■ . POINT

-5.000 V

ELEVATION IN UNITS
D = 1

E = 3
F = 5

~9.OO0 -4. DOS -3*000 ■ -2.000 ' -1*000 0.000 1*000 ■ * , POO 3,000 &.0O0 ■S.OOO

X

Fig. 11.. A maze in which the starting point is outside of the maze and the target point is inside

JPL TECHNICAL REPORT 32-1288

17

■'.4;*.!Wtti

3.CI0® ^

:$>: : £»

Fig. 1 2. Same maze in which the starting point is inside the maze and the target point is outside

18

JPL TECHNICAL REPORT 32-1288

MMP

.'•'■ 3 » OHO : , i **••*■•'-■•. •...;.;...■.., ■ . .. :

■ilttt

iiUlK

;■:>■;■''*" '

^^^^^^^^^^fcpppMfiPiss

•'. ;-..*. ;;pJW>- : ^'v r .i^ r: ^^'..-..'..f:'.i.-..>»-v^ ■.,.-,. ..■,!.. ,.;...,

STARTING POINT j

. : :; '<*:*" v d;c*py ;^ : ix ••••• ■■'■ '■ ? : ; ^•■;- ; t- : ;^:;

| ||||||j| iHlltl llllll Willi lllill ^ 5 ''

D I I

, III

F ^ 5

II

two .

X I

^.i,-ii.*.-:>>v.-

* :

;^Vi^l'^v:' : ^';: ; :vS : v|

Fig. 13. Result of the robot crawling on and over hills

JPL TECHNICAL REPORT 32-1288

19

References

1. Moore, E, F., "Shortest Path through a Maze," Annals of the Computation
Laboratory of Harvard University, Vol. 30, pp. 285-292, Harvard University
Press, Cambridge, Mass., 1959.

2. Lee, C. Y., "An Algorithm for Path Connections and Its Applications/' IEEE
Trans. Electron. Compute pp. 346-365, Sept. 1961.

3. Miller, B. P., et al., Roving Vehicle Motion Control, Final Report TR 67-60.
AC Electronics, Defense Research Laboratories, Santa Barbara, Calif.,
Dec. 1967.

4. Lawson, C. L. ? Block, N., and Garrett, R. S., "Computer Subroutine for Con-
tour Plotting," in Supporting Research and Advanced Development, Space
Programs Summary 37-32, Vol. IV, p. 18. Jet Propulsion Laboratory, Pasadena,
Calif., Feb. 1-Mar. 31, 1965.

5. Freeman, H., and Loutrel, P. P., "An Algorithm for the Solution of the Two-
Dimensional 'Hidden-Line' Problem," IEEE Trans. Electron. Compute
Vol. EC-16, No. 6, pp. 784.-790, Dec. 1967.

20 JPL TECHNICAL REPORT 32-1288