Obstacle Avoidance and Navigation in the Real World by a Seeing Robot Rover, Hans Moravec, 1980
<-- Previous  Next -->

Appendix 1: Introduction

Software Pointers

It has not been possible in this thesis to present all the details of all algorithms which made the cart go. Further information might be gleaned from the code itself. The Stanford AI lab “Dart” archiving system may make the relevant computer files available a number of years after the 1980 publication of this document. Though changes in the configuration of the system will rapidly make many of the programs inoperable, some portions may be salvageable. The names of involved files follow.

SPOTS.SAI[VIM,HPM] is the calibration program. It must be told the name of a camera or a file containing a picture of the spot array seen by the camera, and how far (in inter-spot spacings) the lens center of the camera was from the array. The camera orientation is assumed to be horizontal (by definition), and lens center the same height as the central spot of the array. The program writes out a calibration file.

CRUSH.SAI[MIS,HPM] is the obstacle avoider. It asks for a list of TV receivers, the tilt of the camera from the horizontal (it was $15\deg$ in all my runs) and several other reasonably self evident questions.

CRASHS.SUB[MIS,HPM] is a file of Sail macros used by CRUSH.SAI, which contains most of the actual substance of the program.

CRUSH.SAI also uses a set of externally compiled procedures referenced through the files VIGHDR.SAI[VIS,HPM] (display and image handling utilities), REDPIC.SAI[VIS,HPM] (which facilitates handling sequences of reduced pictures, and also feature description window sequences), DISTOR.HDR[VIS,HPM] (written by Donald Gennery, which derive and apply least-squares camera distortion correcting polynomials), and RD1HOG.SAI[CAR,HPM] (which contains the two-arc atomic path planner, the cart response simulator and the remote control code).

VIGHDR.SAI itself calls in the files PIXHDR.SAI[VIS,HPM] (picture handling utilities; outlined in Appendix 10) and GRAHDR.SAI[GOD,HPM] (the GOD device-independent graphics package, also summarized in Appendix 10). It also calls in VIXFAI.REL[VIS,HPM] (which is a package for displaying pictures in the environment of the older data-disc display package. It is compiled from the FAIL source file VIXFAI.FAI[VIS,HPM]), for one of its minor routines.

PIXHDR.SAI calls in PIXSAI.REL[VIS,HPM] (compiled from PIXSAI.SAI), SQTILE.REL[VIS,HPM] (compiled from SQTILE.SAI) and PIXFAI.REL[VIS,HPM] (compiled from PIXFAI.FAI).

GRAHDR.SAI invokes GRASAI.REL[GOD,HPM] (from GRASAI.SAI) and FILHDR.SAI[VIS,HPM] (an extended file name parser which itself calls FILNAM.REL[VIS,HPM] compiled from FILNAM.SAI).

AVOID.SAI[CAR,HPM] and AVOID1.SAI[CAR,HPM] are demonstration programs for the approximate and exact, respectively, path planning algorithms. They are presented in full in Appendix 8.

NCOARP.SAI[CAR,HPM] demonstrates the interest operator and binary search correlator.

CALTST.SAI[MIS,HPM] produces polynomial-overlayed calibration test patterns, of which Figure 4-4 is an instance.

CART.SAI[TRI,HPM] (using 3DRAW.SAI[TRI,HPM]) generates files which can be used to generate the 3D line drawings and gray scale graphics like the illustrations in Chapter 9. VIEWDD.SAI, VIEWXG.SAI, VIEWMS.SAI, SEEGOD.SAI take these files and produce representations on data discs, the XGP, picture files and GOD files, respectively.

TYPHDR.SAI[GOD,HPM] is an extension of the GOD file routines which allows convenient typesetting of two dimensional text in mixed fonts.

CIRCUT.SAI[GOD,HPM] is another little extension that facilitates drawing of logic and circuit diagrams, such as the one in Figure 10-2. The diagram was actually produced by BATCH2.SAI[DIA,HPM].

Hardware Overview

The cart hardware on which the obstacle runs were based is of even more transient interest than the software. A brief overview is presented here.

The control system is very simple and inaccurate. Packets of six bits are passed from the KL-10 output device known as the CAR, through the Cart Control Interface attached to the PDP10, over a unidirectional CB radio transmitter. These six bits are given the following interpretations: Drive motor on; Reverse/forward; Steer left; Steer right; Slide camera left; Slide camera right.

If both bits are on for steering a centering process takes place, using potentiometers attached to the relevant device and a simple op-amp network. To avoid spurious noise-induced camera motion, the slider is activated only by the protocol: both slider bits off; both bits on; bit for appropriate direction on. After receiving such a sequence the camera slides a number of stepping motor increments indicated by a thumbwheel setting on its chassis; typically 256 steps.

There are only two states for the motors - going or not going. No smooth power control is possible. Because of the current data transmission scheme it is only possible to specify the duration of any motor actuation to an accuracy of at best one thirtieth of second. Thus in general after issuing any control command it is impossible to determine whether the desired action has been carried out. Even assuming that the motors have run for the desired time period the positions of any of the actuators, and the cart itself, are uncertain because of the rough motions caused by switching full power on and off to the motors.

The KL-10 device CAR can be used to control the on-off state of the power transistors labelled 20 through 26 in the cart control interface. Device CAR is activated every tick (sixtieth of a second) and the state of these transistors is updated if indicated by the output buffer. When running, CAR also keeps transistor 18 off. Alternatively CONO's can be used to control transistors 18 through 35 directly, however accurate timing will be lost even if a SPACEWAR module is used.

Transistor 18 operates a relay which when off causes the cart transmitter to be on. The transmitter encoder has its own clock (running at about 1kH). It scans transistors 21 through 26, emitting a short (order of 0.5 mS) pulse before looking at each one, and then idles for either two or four cycles depending on whether the transistor currently under examination is on or off. After looking at the sixth transistor and idling for the appropriate amount of time it emits another pulse and then idles for a longer period before starting the scan again. Thus the six bits are encoded as either short (= 1) or long (= 0) gaps between seven high pulses, with a gap roughly as long as each pulse train between successive transmissions of the train.

The receiver circuitry on the cart passes on this train of seven positive going pulses to the onboard logic. The onboard logic has three six bit registers, call them A, B, and C. Register A is a shift register which receives 0's and 1's decoded from the intergap pulses by some timing circuitry. When a sufficient time has passed, since the reception of a pulse, and if the number of pulses was exactly six, bits in A are taken to be a packet. A single 10 micro-second control pulse is emitted from the timing network. On the leading edge of this pulse, registers A and B are compared. If their contents are identical the contents of B are shifted in parallel to C and the outputs of C, which pass through a static network to drive the relays operating the motors, are enabled by a retriggerable one shot for approximately two seconds. Regardless of the result of the comparison the contents of register A are shifted in parallel into register B on the trailing edge of the control pulse.

Thus the logic compares successive sets of six pulses and when they are identical uses them to control the actuators. Although the retriggerable one shot mentioned above enables the control register C for approximately two seconds, a new pair of successive identical bit packets will overwrite the contents of that register and retrigger the one shot for another two seconds. Thus to terminate some motor activity packets of six zeroes can be sent repeatedly.

In case there is any future interest in this dull hardware, I have left a set of circuit diagrams with Allan Miller of the Stanford AI lab.

<-- Previous  Next -->