A Parallel Processor Algorithm for Robot Route Planning

A Parallel Processor Algorithm for Robot Route Planning,

C.M, Witkowski, Artificial Intelligence Laboratory, Department of Computer Science and Statistics, Queen Mary College, Mile End Road, London E1 4NS, England,

approximated by a circle when the occasion demands, The vehicle is equipped with various sensors, not­ ably an ultrasonic rangefinder and a standard video camera.

A program residing in the robot's 6502 based microcomputer allows the robot to map its environ­ ment using the rangefinder, Figure 1 shows such a map, of one of the offices attached to the labora­ tory, there is a table in the middle of the room. Eight radial scans are made, each comprising 200 rotations of 1,8 degrees followed by a range read­ ing, The figure represents an area of 200 by 200 inches. Throughout this mapping process and route execution the precision and repeatability of the stepper motors is relied on to maintain navigation­ al accuracy.

It was primarily the poor quality of the sensor data obtained as a map that prompted this investi­ gation. It was considered that it would be less effort and the results would be more reliable if a method could be developed that completely avoided the need for detailed analysis and line fitting to this type of data. In the event, and partly due to the availability of the ICL Distributed Array Pro­ cessor (DAP) a cellular representation of the prob­ lem, coupled to a parallel search that spreads through a lattice of free points was chosen.

Figures 2 and 3 show the results of the algo­ rithm, The total robot environment is represented

ABSTRACT

This paper presents a fast, uniform, parallel search algorithm for robot route planning and obs­ tacle avoidance. The algorithm is equally appli­ cable to real or synthetic data and overcomes many problems associated with other route finding methods, The time taken to generate a route through a an arbitrarily complex environment has been reduced to an insignificant fraction of the time taken for the robot to traverse the route. Furthermore the time taken to create the route is independent of environment complexity and only linearly proportional to route length. Actual results and timings from running the algorithm on the ICL Distributed Array Processor and executing the resultant path on a mobile robot are presented.

One of the most important components of the software for a mobile robot system is a route planner, to navigate the vehicle through a com­ pletely, or partially mapped environment. Such programs split into two main sections, the representation of the envi.ronment and a method of searching possible route paths between the current robot position and some new location, avoiding known obstacles,

Well established methods of describing the en­ vironment include approximating all obstacles as polyhedra, Nilsson [1], or calculating m1n1mum enclosing circles or ellipses, Moravec [2], In either case the standard approach to the actual planning is to expand the environment representa­ tion by a 'centre to edge' distance for the robot, Thereafter the robot may be treated as a moving point, rather than a swept volume. Brooks [3] describes a method in which free space is represented by overlapping 'generalised cones'. Matsushima and Oda [4] describe a metho9 for robot motion in an unknown environment using a tactile sensor.

We have a mobile robot with which various exper­ iments may be performed. It is of a very conven­ tional design, Two stepper motors independently drive wheels equidistantly spaced from the mid­ point along the lateral axis. The base, and hence the groundplan, is octagonal measuring 24 inches across the flats. It may therefore be reasonably by a 64x64 lattice of points, some of which will be occupied by obstacles that will have to be avoided during robot motions, These points are shown as asterisks "*"· Lattice points which become occu­ pied during the expansion process, so that the robot may be treated as a point, are shown as "-"· The current or 'start' position of the robot is shown by a "S" and the desired, 'goal' position by "G", Points indicated by "R" are (possibly many) paths from start to goal with equal path lengths, in terms of horizontal, vertical and diagonal move­ ments, Intermediate level robot software will interpolate from "S" to "G" via those route points labelled "X" during route execution,

III Jhe ICL Distributed Array Processor,

The DAP, Reddaway [5], is a highly parallel architecture machine cast in the Multiple Data Sin­ gle Instruction (MDSI) mould, It may be best viewed as a matrix of 64 by 64 single bit proces­ sors linked to a common control unit, each having 16Kbits of memory with a cycle time of 250nS, This memory is shared by the host 2980 processor, entry to the DAP and all I/0 is mediated via this host machine, The DAP may either be programmed in mach~ne code or DAP-Fortran, DAP-Fortran is aug­ mented with a matrix data type (and others) with an implicit 64x64 dimensionality and all elements are processed simultaneously. These may be of type real, integer, character and logical. Various data structures within the program are stored as logical matrices (4096 bits), for instance:

ENVIRONMENT The map as input to the program, ROBOT SHAPE The robot ground plan, GROWN-WORLD ENVIRONMENT expanded by ROBOT SHAPE, FROM POINT - Single bit set indicating start node, TO POINT - Single bit indicating goal node. ROBOT PATH - Potential path points, NODE MASK - Robot turn points.

IV The Algorithm.

The algorithm proceeds in the output from each being a then represents some state point in the lattice. a number of stages, logical mask, each bit of its corresponding

Step 1 - Environment expansion - the ENVIRONMENT mask is shifted (using the DAP's inbuilt planar shift functions) by an amount specified by the various bits set in ROBOT SHAPE and the result log­ ically ORed with GROWN WORLD, The effect of this routine is clearly seen in figure 3.

Step 2 Endpoint checks TO POINT are logically ANDed with true result indicates that the robot FROM POINT and GROWN WORLD, a either is, or is being sent to somewhere it cannot be,

Step 3 - Lattice search - This is a two pass routine. Before each pass an integer matrix (SPREAD) is set up that will indicate the distance of each unoccupied lattice point from the start, it is initialised to some large value.

Step 3,1 first pass -Beginning with only FROM_POINT set, each of its eight directly connected neighbours are tested, The value for each point in SPREAD is updated with a new path distance back to the start point if it is 1) a free point, and 2) it is previously unvisited and 3) the new distance is smaller than its current estimate, Each of the

................................................................

-·

---·

................................................................

eight directions is tried in turn, though all lat­ tice points are evaluated in parallel, diagonals are increased by square root two times the horizon­ tal or vertical. The search then proceeds itera­ tively from the points newly reached as a spreading wavefront. Termination occurs when there are either no new free points (in which case the start

was enclosed), or the goal point is reached.

Step 3.2 - second pass - Rather than organise a system of backpointers, in the second pass start is set to TO POINT and the goal to FROM POINT and the process Ts repeated to produce a second SPREAD matrix, whose values indicate shortest path dis­ tances to the goal.

Step 3.3 - determining the path - The least cost path, or paths, within the constraints of the lat­ tice representation, is indicated as all those lat­ tice points whose value in the sum of the two SPREAD matrices equals that in the TO POINT point. These points on the lattice are indicated in fig­ ures 2 and 3 by alphabetic characters. Each of these points, saved in ROBOT PATH, represents a path through the lattice to the goal that be be reached from the start with an equal number hor­

izontal, vertical or diagonal movements.

Step 4 - Generate actual robot path - The algo­ rithm generates a list of lattice points on the route path that most closely corresponds to a route finder which traverses between object corners. To achieve this concavities in the ROBOT PATH mask are detected, by recognising path points in a 3 by 3 neighbourhood, various patterns of the nine bits indicate these situations. These lattice points are indicated in the NODE MASK mask. This parallel operation gives no indication as to route order, neither is any indication given of the presence of

multiple iso-valued paths.

Step 5 One further pass is made through the ROBOT PATH mask from start to goal. The order in which-lattice points at which the robot will change direction is found and their coordinates recorded in the robot command buffer. Multiple paths are detected by a blob counting method at each stage in this expansion. A split in the path is indicated by multiple blobs, one is selected arbitrarily, the others tagged as inactive, these tags are propagat­ ed along the redundant paths until they merge again with the selected path. Only direction change points from NODE MASK on the active path are transferred to the command buffer. A pretty-map routine is then used to generate the output seen in

figures 2 ·and 3.

V Advantages of this algorithm.

It enables a uniform treatment of synthetic (figure 3) and real (figure 2) data. The real data has undergone only minor pre-processing, two passes of an algorithm that removes ·noise' points, those with less than two neighbours.

The expansion algorithm is independent of en­ vironment complexity, rather computational effort is proportional to the number of points set in the

robot ground plan.

Search time for the route points is linear with respect to the number of lattice points traversed from start to goal, this is in turn a good measure of the actual distance the robot will have to move.

In general robots with assymmetric ground plans

need additional methods, although the algorithm is suitable for assymetric robots which mov~ by pure translation, Lozano-Perez and Wesley [ 5], this would be trivially achieved by offering a modified ROBOT SHAPE mask as input.

Plans may be generated at different resolutions by a simple rescaling of the environment data. A

rescaling has been made between figures 1 and 2.

Very advantageous timings are achieved, which are in part offset by the fact that the DAP may

only be used in batch mode.

For these 64 by 64 maps the program timings may be split into three parts. First system overheads (conversions between DAP and 2980 Fortran storage modes etc.), about 22 milliseconds/run; second a fixed time component of 20 mS/run, (16 for expan­ sion, one extra for noise reduction on real data). The third component depends on the number of expan­ sions between start and goal, observed timings are 2.035mS/expansion to generate ROBOT PATH and 0.309mS/expansion for the final pass along ROBOT PATH.

The synthetic data path (figure 3), with 146 expansions took 0.387 seconds of DAP processor time, the robot makes 18 changes of direction and traversed the 481 inch path in 188 ~econds. The real data (figure 2), with 50 expansions required 0.158 seconds of DAP processor time, the robot makes five changes of direction and traversed the 151 inch path in 62 seconds.

In both cases the lattice is on a three inch grid spacing.

REFERENCES.

1. Nilsson N.J. (1969) "A mobile automaton: An application of artificial intelligence techniques". IJCAI-1969, pp509-520.
2. [2) Moravec H.P. (1981) "Robot Rover Visual Navi­ gation". UMI Research Press, Ann Arbor, Michigan.
3. Brooks R.A. (1982) "Solving the find-path problem by good representation of free space".
4. AAAI 1982, pp381-386.
5. Matsushima K. and Oda M. (1982) "Path finding algorithm for a mobile robot with tactile sensor". Proc. 2nd. Intl. Computer Engineering Conf., 1982, ASHE. pp49-52.
6. Reddaway S.F. (1973) "DAP -A distributed array processor". Proc. 1st. Annual Symposium on
7. Computer Architecture. PP· 61-65
8. Lozano-Perez T. and Wesley M.A. (1979) algorithm for planning collision-free paths polyhedral obstacles". Communications of the "An among ACM,
9. 22-10, pp560-570.