Terrain Navigation Through Knowledge-based Route Planning

TERRAIN NAVIGATION THROUGH KNOWLEDGE-BASED ROUTE PLANNING

JOHN f. GILMORE AND ÄNTONIO C. SEMECO

ÄRTIFICIAL INTELLIGENCE ßRANCH GEORGIA TECH RESEARCH INSTITUTE ÄTLANTA, GEORGIA 30332

This paper describes a dynamic route planning and executlon system called TREK (Tech Route Execution Kaleidoscopel. TREK consists of four distinct processing phases: (1l scene recognltion, (2l route generatlon, (3l scene matching, (4l and know I edge-based va I i dat Ion. Each of these processes is discussed in the following sections.

~Q SCENE RECOGNITION

The recognltion of objects in an Image is central to the concept of local route piannlng. Given that a global route can be generated through a I arge area of terra In, scene recognition must be capable of interpretlng the objects contained wlthin the current field-of-view so that they may be avoided during the traversal of the actua I terra In. W i thout a capab i I i ty to determine what is in its local environment, low Ievei route pianning would not be able to avoid threatening objects or objects obstructing the vehicle's path.

Scene classiflcation in the TREK system exploits a hierarchical classlflcation tree consisting of objects and regions divided into natural or man­ made categories. Efforts in scene classification to date have concentrated on detectlon and classlficatlon in video imagery. This work will be extended to infrared imagery in the near future.

~Q ROUTE PLANNING

The goal of a route planning system is to analyze all available Information to produce a route that I s opt I ma I in I I ght of predetermined mlssion requirements. The TREK route planning system consists of three stages: Al point generation, Bl graph generatlon, and Cl heuristlc search.

A. Point Generation

The TREK system generates three different types of path points: two-sweep points, convex terrain points and crossover exposure points. The two-sweep point generation algorithm is a humanistic approach to terrain traversal assuming that the system possesses a map and a compass. The centra I i dea of two-sweep i s the assumption that the dlrectlon of the goai point can always be determined through

ABSTRACT

The advent of advanced computer architectures for parallel and symbol ic processing has evolved to the point where the technology currently exists for the development of prototype autonomous veh icles. Control of such devlces will require communication between knowledge­ based subsystems ln charge of the vlsion, p l ann i ng, and confl Iet resolutlon aspects necessary to make autonomous vehlcles functional in a real world environment. This paper describes a heuristic route pianning system capable of forming the planning foundation of an autonomous ground vehicle.

INTRODUCTION

An effective route planner must address two Ieveis of planning. At the high Ievei, the planning algorithm usuaily exploits some form of map data to generate a global route which avoids mountains, valleys, and canyon areas. Dependlng upon the map resolution, individual pixel path points at this Ievei vary from a representation area of 100 by 100 meters to 12.5 by 12.5 meters. At the low Ievei, the pianning algorithm must deal with local planning Inside these Individual path points so that obstacles such as trees, rocks, and holes may be avoided.

A consensus exlsts that global Information in the form of a digltized terrain map is essential in the operation of an autonomous vehicle, at least at the global Ievei of route planning [1-4]. The terraln map requlred must be capable of representing huge amounts of multidimensional data in a format easlly exploited by the route planner. ln order to make it suitable as a basis for real-time decision making durlng vehicle operation, the data should also be preprocessed lnto a more compact and manageable format. Two interesting approaches to this problern are the ruie-based creation of a "composite map" [3] and the transformation of a polygonal obstacle map into a relational graph database [1]. lt is to the second concept that our current approach to preprocessing map data is more closely allgned.

simple geometry. The algorlthm Initial ly scans torward from lts current locatlon untll lt locates the goal polnt or encounters an obstacle. The underlylng heurlstlc ls the simple strategy that a person uses when there ls an obstacle in front that prevents hlm/her to go to the deslred destlnatlon. The Individual usually goes around the obstacle followlng lts contour untll the destlnatlon ls visible. Thls approach can be used both at the local and global Ievei in route plannlng, but only the global appllcatlon ls dlscussed in thls paper.

The convex polnts of Interast for an obstacle are deflned as the set of polnts on the obstacle 1 s boundary such that: a> each polnt in the set ls a convex polnt, b) for each polnt P in the set, p 1 s curvature ls a local maxlmum, and c) the set of polnts forms a convex polygon.

A set of convex polnts ls generated for each obstacle in the terraln Image. An obstacle ls represented as a Iist of (x,y) coordlnate palrs whlch deflne lts boundary. Thls set of polnts does not have tobe of a contlnuous nature, but lt ls assumed that the dlstance between adjacent polnts ls uniform.

The comblnatlon of two-sweep and convex polnt routes produces an extensive route graph wlth a number of route segment lntersectlons. These lntersectlons or crossover polnts actually represent high trafflc areas of maxlmum exposure. By connectlng al I crossover polnts wlth a llne-of-slght algorlthm, a number of offensive route optlons are created~ When merged wlth defensive path polnts produced by two-sweep and convex polnt generatlon, an unbaslsed route graph Js generated. ln thls mode the TREK system ls capable of non-ml lltary route pla~nlng as would be the case in a robot veh lcle patroll Jng a national park looklng for stranded motorlsts.

B. Graph Generation

A global terraln Image graph based upon the aforementloned polnt sets ls generated uslng a Jlne-of-slght computatlon ls made to determlne lf a path exlsts between Individual obstacles polnts-of Jnterest. A cost ls then asslgned to each edge in the graph. Thls cost ls computed as a welghted functlon of dlstance, terraln, scenarlo threats and vehlcle constralnts as follows:

F<c> Dls~ance Threa~s * W1 + Terrain * W2 + * W3 + Cons~raln~s * W4

Thls crlterla edge graph forms the search space for the A* algorlthm.

C. Heurlstlc Seereh

Once the search graph has been constructed, a sultable search procedure must be used to find an optimal route.

Glven the lmportant to he I p search. expected slze of the graph, lt ls to have cost estlmate functlons Jmprove the efflclency of the

The A* algorlthm was chosen as the heurlstlc search mechanlsm ln TREK. A* ls bas I ca I I y a best-f I rst tree search algorlthm augmented to handle cycles and dupllcate paths between nodes. lf a recently dlscovered path to node N Js found to be an Jmprovement over a prevlous path to the same node. the polnter from N to lts predecessor Js updated and the Jmprovement Js propagated to other paths that have N as an IntermedIate node.

~~SCENE MATCHIN2

One of the most Jmportant aspects of an autonomous vehlcle system ls lts abl I lty to malntaln and fol low the routes that Jt generates. lf a vehlcle ls lncapable of performlog thls task, Jt wl II eventually wander almlessly through terraln that lt can not recogn I ze as nothIng w I I I match l ts global map. For thls reason, an accurate scene matehing algorlthm must be lncorporated lnto the system.

The symbo I I c process I ng nature of the TREK system readl ly Iands ltself to a syntactlc pattern recognltlon approach to scen e match I ng As th e goa I In scene matehing ls to perform an Jmage-to-Jmage mapplng, plxel correlatlon technlques are probably the most accurate method avallable. The dlfflculty for autonomous vehlcle appllcatlons ls that the local sensor Image ls guaranteed to have a different perspectlve than that of the global altltude data map belng matched. Such a perspectlve Invariant requlrement Js the shortcomlng of most conventlonal scene matehing approaches.

The key to determlnlng and malntaln the vehlcle's posltlon ls to match objects and reglons detected durlng scene classlflcatlon to objects and reglons in the map. Th I s can be accomp I I shed by representlng each object and reglon as a classlfled polnt, constructlng a perspectlve Invariant graph of the local Image polnts, and comparlng the local graph as a subgraphtobe located in a global map graph whlch has been created Jn the same manner [5]. Thls time of a local-to-global scene match lng I s accurate In I I ght of obscuratlons and other posslble terraln permutatlons and easl ly performed uslng a symbol Je processlng language such as LISP.

~~ KNOWLEDGE BASEQ YALIOATIOH

Scene recognltlon, route plannlng, and scene matehing Information constltute the global database of the TREK system. Thls Information Js processed by the system as a prel Jmlnary representatlon of the current vehlcle envlronment. Tasks or mlsslon goals are provlded to the system through communlcatlng problern requlrements via the control strategy. For a ml I Jtary scenarlo, example mlsslon goals would be as follows:

PRIMARY GOAL: patrol zone 410

SECONDARY GOAL: neutral lze lntruders

SECONDARY GOAL: maxlmlze survlvabl llty

SECONDARY GOAL: maxlmlze kll I ratlo

TREK lnterprets these mlsslon requlrements and determlnes the optimal mlsslon parameters whlch are passed to the scene recognltlon, route plannlng, and scene matehing algorlthms. An lnl~lal plan of actlon ls then generated and represented in the global database. Declslons the on valldlty of the scene Interpretation and the current plan of actlon are made through knowledge base processlng. The TREK knowledge base contalns three types of r u I es : s ce n e r u I es, m I s s Ion r u I es, an d survlvablllty rules.

Scene ru I es are used to va II date and further Interpret the Information provlde by scene recognltlon. ln natural terraln Images, object classlflcatlon confldences can be enhanced through the utl I lzatlon of positive and negative evldence provlded by scene context. For example,

SCENE RULE 98

IF [1] an object ls man-made and

[2] lt ls on a road or in a fleld and

[3] lt has a high confldence of motlon,

THEN [1] hypothesls the object ls a vehlcle [2] lncrease target confldence

Missfon rules Interpret the generated plan in light of high Ievei mlsslon goals. For example, the detectlon of three threats w II 1 generate a p I an of act Ion to engage and neutrallze the threats based upon the prevlously entered mlsslon plan. Missfon rules further analyzed the system goals by examlnlng t be requested survlvablllty and kill ratlo Ievels and creatlng a modlfled plan through system feedback. For example,

MISSION RULE 132

• IF [1] multiple threats are detected and [2] they are in a column and
• they are in possess motlon and
• they areapproachlog an area that will maxlmlze kill and survlvablllty
• THEN [1] generate a defensive route to that area and
• determlne the threat time of arrlval to that area and
• generate an offensive route to maxlmlze kll I tobe executed on threat arrlval

Mission plans arealso used to repalr plans based on I nva I I d lnterpretat Ions or changes in a scene.

Survlvablllty rules are maxlmlze the vehlcles chances based on the Interpretation of envlronment. For example, rules that of survlval the current

SURVIVABILITY RULE 122

• IF [1] an object ls detected and
• avoldance wll I delay accompl lsh­ ment of mlsslon goals
• THEN [1] determlne lts probabl llty of threat and
• replan to avold lf threat ls greater than (.5)

Based upon the results of knowledge base process lng, the control strategy w II I feedback adjusted parameters ~o scene recognltlon, route plannlng, or scene matehing algorlthms for updated Information, or execute the plan and communlcate thls declslon to the user for approva I.

SUMMARY

Thls paper has presented a high Ievel vlew of the TREK terraln navlgatlon system. TREK [1] analyzes a digital terraln map to generate a global route, [2] performs scene Interpretation to generate local routes, [3] malntalns a track of lts posltlon through scene matchlng, and [4] uses knowledge base processlng to val tdate and lmprove prellmlnary plans in light of predetermlned mlsslon goals. The entlre TREK system was wrltten in LISP on a Symbol lcs 3600 and ls currently belng enhanced to lncrease lt vlsual recognltlon capabllltles, broaden lts Interpretation of mlsslon goals, and advance lts temporal r e a so n I n g pro ce s s · Ne a r t er m p I a n s I n c I u d e the transportatlon of the entlre TREK system lnto a two functlonal mobile robots (possesslng additional sensory Inputs) that has recently been donated by IBM for research in materlals handfing and ·flexible manufacturlng appllcatlons.

REFERENCES.

[1] Meystel, A. and Holeva, L.,"lnteract­ lon between Subsystenos of VIsion and Motion Plannlng ln Unmanned Vehlcles wlth Autono­ maus lntelllgence",SPIE Appllcatlons of Al, Washlngton, D.C., May 1984.

[2] Mitchef I, Joseph s. B. and Kelrsey, Davld M.,"Plannlng Strategie Paths through Variable Terrain Data",SPIE Appllcatlons of Al, Washlngton, D.C., May 1984.

1. Denton, Rlchard V. and Froeberg, Pater L.,"Appllcatlons of Artlflclal lntelllgence in Automated Route Plannlng",SPIE Appl lca­ tlons of Al, Washlngton, D.C., May 1984.
2. Kelrsey, D.M., Mltchell, J.S., Payton, D.W. and Preyss, E.P.,"Multl-level Path Plannlng For Autonomaus Vehlcles",SPIE App­ llcatlons of Al, Washington D.C., May 1984.

[5] Gllmore, John F.,"Syntactlc Pattern Analysis As A Means Of Scene Matchlng",Can­ adlan Soclety For Computatlonal Studles Of lntelllgence,Saskatoon, Canada, May 1982.