Autonomous Robots 3,79-89 (1996) @ 1996 Kluwer Academic Publishers. Manufactured in The Netherlands.

Case-BasedPath Planning for Autonomous Underwater Vehicles* C. VASUDEVAN AND K. GANESAN

Department of ComputerScienceand Engineering, Florida Atlantic University, Boca Raton, FL 33431 [email protected] [email protected]

Case-based reasoning is reasoning based on specific instances of past experience. A new solution is Abstract. generated by retrieving and adapting an old one which approximately matches the current situation. In this paper, we outline a case-based reasoning scheme for path planning in autonomous underwater vehicle (AUV) missions. An annotated map database is employed to model the navigational environment. Routes which are used in earlier missions are represented as objects in the map. When a new route is to be planned, the path planner retrieves a matching route from the database and modifies it to suit to the current situation. Whenever a matching route is not available, a new route is synthesized based on past cases that describe similar navigational environments. Case-based approach is thus used not only to adapt old routes but also to synthesize new ones. Since the proposed scheme is centered around reuse of old routes, it would be fast especially when long routes need to be generated. Moreover, better reliability of paths can be expected as they are adapted from earlier missions. The scheme is novel and appropriate for AUV mission scenarios. In this paper, we describe the representation of navigation environment including past routes and objects in the navigational space. Further, we discuss the retrieval and repair strategies and the scheme for synthesizing new routes. Sample results of both synthesis and reuse of routes and system performance analysis are also presented. One major advantage of this system is the facility to enrich the map database with new routes as they are generated. Keywords:

path planning, case-based reasoning, autonomous robots, route planning

1. Introduction Path planning is a classical problem in robotics and autonomous vehicles. Given a cluttered environment with obstacles, the problem is to synthesize an obstacle-free path (route) considering the constraints of the vehicle/robot and other navigational parameters. Path planning problem differs from obstacle avoidance schemes in the sense that the former refers to preplanning in a known environment and the later refers to reactive navigation in an environment with unknown obstacles. Hwang and Ahuja (1992) have provided an extensive survey on path planning for land vehicles. Conventional approaches are mostly algorithmic which attempt to optimize travel distance, travel time, or both *This work was supported in part by National Science Foundation Grant No. BCS-9017990.

and require detailed models of vehicle dynamics and navigational environments. These models are difficult to obtain and often computationally intensive. Some route planning schemes suggested for Autonomous Underwater Vehicles (AUVs) are artificial potential fields method (Warren, 1990), dynamic CRP model (Qiu and Feng, 1991), and A* algorithms (Carol1 et al., 1992). The path planner developed by Carol1 et al. (1992) employs information regarding bathymetry, exclusion zones, obstacles, and ocean current stored in separate databases. A quadtree organization is used to represent depth and obstacle information. The inputs are start task point, a goal task point, a set of constraints such as minimum and maximum depth, different desired speeds, and fuel resources. The planner attempts to generate a minimum cost collision free path using A* search algorithm. A path is considered collision free if

80

Vasudevan and Ganesan

it does not cross obstacles, active exclusion zones, or ‘and masses. In another approach, Warren (1990) uses the potential fields to represent collision-free paths. Here, obstacles are assumed to carry electric charges and the resulting scalar potential field is used to represent the free space. Collisions between the obstacle and the robot are avoided by a repulsive force between them which is the negative gradient of the potential field. In this scheme, path planning is done at two levels; a global planner selects a path from the minimum potential valley and a local planner modifies this path to derive the final one. If the local planner fails, a new path is selected by the global planner. The free space is represented by a graph consisting of a finite number of nodes and edges. Each node is assigned a cost depending on the width of the free space at the node. A candidate path is one that minimizes both the path length and the chances of collision. Case-based reasoning is relatively a new approach to path planning. An example is ROUTER 2 (Goel and Callentine, 1992) which generates new routes for robot navigation using old plans stored in memory. The geographical locations are abstracted to neighborhoods and pathways for the purpose of indexing at the highest level. The case memory is organized according to a spatial hierarchy based on relative significance and vicinity of pathways. An enhanced version of this planner-ROUTER 4-uses an integrated approach combining both domain model as well as past cases. Domain knowledge is in the form of a spatial model of the geographical space representing qualitative information on streets, their directions, and intersections. Streets are grouped into neighborhoods and neighborhoods are organized in a neighborhoodsubneighborhood hierarchy. The cases are indexed by the neighborhoods. Cases are retrieved based on their closeness to the start and goal locations. The adaptation is through combining more than one case each of which solves part of a problem. Since the system uses entire path from each case, the paths generated may be suboptimal. A method selector chooses either the CBR planner or model-based planner based on availability of old cases in the casebase. Haigh and Veloso (1993) explain a scheme that integrates analogical reasoning to prune search space in path planning from road maps. An old case is used as guidance for search operations with the anticipation that one solution path will often be a subpath of another problem. It has been reported that the use

6

of analogy reduced the computation time to about a minute compared to an hour needed in breadth-first search approach to planning near-optimal routes from a map with 48 intersections and 60 road segments. Storing paths for use in future navigation is employed with a learning perspective in another work (Chen, 1992). An integrated approach combining cases, rules, and Dijkstra algorithm has been reported by Liu et al, (1994). The complexity of blind search of Dijkstra’s algorithm is improved by incorporating common sense knowledge and knowledge about geographical situations. The search space is pruned by old cases also. In situations where a partially matching old case is available, the Dijkstra’s algorithm is used to search for the remaining part alone. The Case-Based Route Finder tries to retrieve a matching case and employs Dijkstra’s algorithm to fill in the missing segments. Each of the junctions are numbered and the cases are simple lists of these junctions which are different routes compiled earlier. An experimental route planner for an autonomous vehicle was reported by Chappel (1987) in which a high level mission specification is broken down into a route consisting of way points. The system is based on blackboard architecture and implemented in Lisp. Kao et al. (1992) describe a simple approach to planning and executing complex AUV missions based on userdefined scripts rather than sophisticated algorithms. They use layered control architecture for arbitration between conflicting scripts. Pouliot and Smith (1992) describe an integrated mission planning architecture for unmanned underwater vehicles. A mission planning node is connected to UUV using acoustic, fiber optic or RF communication links. Data compression technologies are used to meet the data transfer requirements. Multi-layered databases are used to store past and current environmental data. Mission planning and replanning are done by human operators as needed in real time to adjust to new information or changing sea conditions. Quinn and Lane (1994) adopt a distributed approach for motion planning in coupled AUVmanipulator systems. They examine the computational requirements of high DOF systems and present a technique based on local motion planning search which allows fast execution of motion plans. Distributed search is achieved through the execution of a number of subsearches in parallel, where each subsearch contains a unique subset of the DOFs in the system. The CBR approaches mentioned above are for land navigation with static information about highways,

Case-Based Planning for AUVs

roads, junctions, and location names. Underwater navigation is quite different from that of robots or land vehicles due to the specific nature of the environment and the characteristics of the vehicle. Poor visibility, complex position locating strategies, and environmental factors such as water current that affect the vehicle dynamics are among the specific features of underwater navigation. There are no pre-determined routes and the traveling distances are often much longer compared to those of mobile robots or land vehicles. Moreover, the underwater environment is relatively less cluttered providing a more flexible navigation. Often, past routes can be reused in future missions with minimal adaptation. Hence, a case-basedpath planning is quite appropriate for AUVs. The scheme implemented here, generates route plans by modifying old routes or by synthesizing a new plan based on old navigational situations. Old routes are stored as objects in an annotated map database which supports spatial representation and geometric queries. Annotated map database facilitates a unique spatial indexing for geographical information cases. The spatial representation of casebaseand the ability to synthesize routes if no matching ones are available make this work distinct from the ones described above. 2.

Case-Based Reasoning

Case-based reasoning relies on specific instances of past experience to solve new problems. A new solution is generated by retrieving and adapting an old one which approximately matches the current situation. This often results in faster synthesis of solutions compared to rule-based reasoning or reasoning from first principles. A case is selected based upon how well the features, the goals, and the constraints associated with the case match with those of the current problem. A typical case-based reasoning process can be explained as following. The casebaseis an episodic memory that represents past experience. The cases in this library are stored and accessed using specific indices. These indices are derived based on several considerations such as the salient features of the case, the type of problem solving, the utility and uniqueness of the case, failures encountered, and other context-specific information. When a new problem is given, relevant indices are extracted from its features by applying a set of indexing rules. These indices are then used to retrieve fully or partially matching case(s) from the

81

case library. The candidate cases are evaluated and the best one is selected. The selected case may need some modifications to conform to the new situation and the modifications are performed using a set of repair rules that represent the domain-specific models or heuristics. CBR has a learning phase also which involves updating the case library with the modified case if it is found worthwhile. Thus, learning is through accumulation of new cases (experience) and through new ways of indexing. The major issues related to the design of a case-based reasoning system are: representation and organization of cases, indexing, retrieval and evaluation of candidate cases, and repair of selected cases. CBR has been successfully applied to various problems in planning, design, diagnosis, decision making, prediction, real-time control, and intelligent information retrieval (Kolodner, 1988; Hammond, 1989). In real-time applications such as AWs, the strategy of choosing, modifying, and adapting an approximate plan from the plan repository will be faster than building a plan starting from scratch. For AUVs, in particular, different missions would share many common tasks and hence an adaptive planning such as CBR is very attractive. In most underwater missions, the probability of traveling between the same start and destination points is quite high. Often, we prefer a familiar solution that is sure and certain over something totally new and presumably better. Case-based path planning has further significance for AUV scenarios. The optimality of traveling distances may not have much relevance, because of two reasons. First, the environment is often not very cluttered, leading to short line-of-sight paths. Second, the savings resulting from optimization efforts are fairly small compared to the long distances of travel in AUV missions. These aspects should be taken into consideration while selecting the way points (intermediate points in a route). The vehicle dynamics put certain restrictions on the maximum speed, turning angle, and the maximum depth. It is difficult to obtain an accurate model that accommodates all these factors. Under these circumstances, the best choice is to rely on well-laid out practices and patterns. The case-based approach described here is quite appropriate in practical field missions.

3.

Path Planning

Functionally, there are four parts for navigation: path planning, position location, perception planning, and

82

Vasudevan and Ganesan

obstacle avoidance. All missions involve cruising to one or more target sites, maneuvering the vehicle at the target site, returning to the launch site, and finally, docking the vehicle. Preplanning of routes is necessary to simplify the navigational command and control functions and to conserve the computational time and efforts needed during a mission. The objective of path planning is to compose a collection of way points from start to goal location that form an obstacle free path The path planner also needs to determine the length of different path segments and the desired speed of navigation while computing the way points. The Case-Based Path Planner discussed here is characterized not only by retrieval and repair of past routes but also by case-based synthesis of new paths whenever acceptable routes could not be retrieved. Thus the planner is capable of handling situations where an appropriate matching past cases are not found in the casebase. In such cases, it generates a new route by attaching new segments to old ones as well as joining path segments belonging to different routes. This facility to fall back from plan repair to plan synthesis helps to reduce the failure rate and excessive tweaking of old cases. Moreover, it is important to note that synthesis of new segments/routes is also based on case-basedreasoning method. The casebasefor synthesis represents

start, end

Figure I.

8

Path planner-system

organization.

waypoints

typical design parameters and the environment in which they are applicable. The following sections describe the system configuration, details of representation, and reasoning mechanisms employed in our design. 4.

System Configuration

A functional block schematic of the path planner is shown in Fig. 1. Given a pair of start and end points, the planner outputs a set of waypoints to navigate between them. The annotated map database stores routes used in past missions and information about obstacles in the navigation region. The route evaluator rates different candidate routes (if available) to select the best one. Route adapter checks the segments of the selected route to verify that each of the path segments conform to the constraints specified. Segment synthesizer determines the maximum length of segments based on cases in the navigational casebase and computes the next waypoint. This module is also responsible for modifying the straight line path segment for avoiding any obstacles present in its trajectory. Segment composer picks up appropriate path segments to compose partial routes. The map update module takes new routes as input, creates corresponding route object

Case-Based Planning for AUVs

and path segment objects, and stores them in the map database. 5.

Representation

An annotated map database stores the information about the navigation environment and routes used in past missions. This map has a facility to represent various kinds of objects in a spatial format that facilitates efficient and flexible retrieval of information. This makes it possible for the path planner to retrieve past cases of routes as well as to determine the presence of obstacles along the routes. Path planner also has a case-library of past design situations for the purpose of synthesizing new path segments. 5.1.

Annotated Map

The annotated map serves as part of the case-library needed for the path planner and is composed of an object database, a grid database, and a depth database (Ganesan et al., 1992). The object database holds information about object descriptions and their attributes (annotations). Objects of various shapes and types can be represented in the map. The six standard shapes currently supported are point, line, circle, rectangle, box and cylinder. Each object description, in addition to its geometric details, contains annotations that help perception and navigation, These annotations have a value-attribute structure which can be used to describe any information that is of interest in recognizing or using the objects. A collection of objects can be represented as a composite object to facilitate referencing them as a group. This has specific significance to path planning problems where a route can be represented as a composite object consisting of a sequence of path segments (line objects). In order to support spatial queries, the map has a grid database in which objects are mapped into the grid cells they occupy. Objects recorded in the object database are mapped into regular grid format. The 3-D objects are, in fact, mapped into a 2 i-D representation (an X-Y grid with a range or height information) in order to conserve storage space. The grid database is hierarchical supporting multiple levels of resolution. The annotated map database supports geometrical queries that retrieves spatial information about the objects in the map. A typical query may look like “Retrieve all objects within a circular region of radius 100”. These queries are useful in many navigational tasks like path planning, position location, object recognition, etc.

5.2.

83

Routes

A route is defined in terms of its start and end points and the path segments that constitute the trajectory between them. Each of these path segments are represented as a Line Object with its start and end points. Since every route and path are stored as objects in the map database, they have distinct object IDS. There are two-way links between a route and its path segments through ID numbers, i.e., a route has IDS of all its path segments and conversely, a path segment has the ID of its parent route. These IDS are part of the annotations of these objects. The annotations attached to a route object include information such as total distance, maximum speed and depth, travel time, source and destination locations, and other navigation-related information that help to determine the usefulness of the route for a given situation. This information is usually based on the strategies and heuristics of route selection for underwater navigation. Typical descriptions of a route object and a path segment object are given in Tables 1 and 2. Table1. Route object. Object ID Object name Object class Link element IDS

23 Route Composite 54,678,97,33

Annotations: Start

(200,300,50)

End

(2800,4100,50)

Total length

5250

Average speed

40

Maximum speed

53

Maximum depth

270

Quality index

6.9

Table2. Path segment object. Object ID Object name Shape Object class

54 Path-segment Line Reference

Start point

200,300,50

End point

300,380,65

Annotations: Parent ID

23

Average speed

45

84

Vasudevan and Ganesan

Table 3. Representation of an obstacle and its annotations. Object ID

Value

Cylinder

Speed of water current

High

Object class

Reference

Direction of water current

Medium

Object state

Active

Depth

Shallow

Present vehicle speed

240

Clutter

Sparse

Dimensions: Center point

500,900.0, 0.0

Large

Radius

100.0

New vehicle speed

100

Height

175.0

Segment length

Small

Annotations: Path

(430 750 0 350 900 0 40010000 45011000 550 1100 0 600 1000 0 700 900 0 570 750 0)

Obstacles

Obstacles are also stored as objects in the map. In addition to the shape details, objects have annotations that provide safe waypoints to navigate around them. These waypoints include the ones used by vehicles in their past missions as well as the prototypical routes computed and placed by human navigators. From a case-based planner point of view, the information such as the paths used in the past to avoid obstacles are more useful and relevant than the exact shape and size of the obstacles. An example object record that describes an obstacle is shown in Table 3. Cases of Navigational Situations

The design of new routes involves determining the desired path segment lengths and the vehicle speed along various segments. The design of a path segment needs to consider the vehicle parameters and the current operating environment. The strategies are exemplified by a set of design cases (typically past experience) that represent design choices in different situations. These design cases are stored in a case-library for use by the path planner. An example of a typical design case is shown in Table 4 During an AW mission, the vehicle position need to be ascertained at regular intervals of time. These intervals should be short enough so that the trajectory of the vehicle can be corrected before the accumulated error in the transit path exceeds certain acceptable limits. The vehicle speed, the clutteredness of the 10

Attribute

4 Navigational error rate

Shape

5.4.

An example design case.

Obstacle

Object name

5.3.

Table 4.

environment, the speed and direction of water current, the positional accuracy needed, and the error rates in vehicle control are some major factors that influence the frequency of position correction which in turn put an upper limit to the length of each path segment. The case frame thus has two parts; the first part represents the context in which the case is applicable and the second part indicates the typical values of the design parameters. Conspicuous from the example case given above, the parameter values are represented in qualitative terms rather than in numerical figures. This abstract representation would help to cover relatively general scenarios applicable to a wide range of problem contexts. Details of this fuzzy indexing scheme follow.

5.5.

Fuzzy Set Representation of Indices

Consider the problem of identifying search indices from the current context. The objective is to successfully retrieve a matching case that minimizes the repair as well as avoids possible failure during its evaluation and execution. The obvious requirement is that the casebase should be rich and varied to cover a broad spectrum of problem scenarios. Using fuzzy sets, specification of indices provides an interval within which matching occurs. Moreover, the fuzzy set membership function establishes a preference within the interval as to the degree of match. Matching becomes graded instead of all-or-nothing. Thus each index can be both general and specific. General in the sense that a large range of values may match to a nonzero degree and specific in the sense that only a small range of values match to a high degree. Overlapping the boundaries of the fuzzy indices allows multiple partial matches that can be aggregated, rated, and ranked.

Case-Based Planning for AUVs

The case library can cover the input space with fewer cases. Also, it provides flexibility in tuning the performance by adjusting the fuzzy set membership definitions (Vasudevan et al., 1994). Fuzzification of specific values of parameters helps in arriving at more abstract and general characteristics. For example, in a typical AUV path planning problem, the factors like depth of travel, speed of water current, etc., can be defined as fuzzy sets based on relevant ranges of values and interpretation by expert navigators. The fuzzy set representation of case indices leads to smaller casebases and a flexible scheme of generalization. Moreover, the approach facilitates the use of standard fuzzy set operators to evaluate candidate cases to arrive at the best matching one. 6.

Adaptation

of Old Route Plans

To plan a route between a given pair of start and end points, the planner first retrieves matching past routes, selects the most suitable one, and then adapts its way points to generate a new route. In order to collect matching cases, the grid data base is queried to retrieve Line objects (representing path segments) within the two regions around the start and end points. These line segments are examined to identify the routes that pass through these two regions. This is possible since each line segment has the ID of the route it belongs to. Once these routes are identified, corresponding descriptions and annotations of the route are retrieved from the object database for evaluation. Three possible outcomes of a search for past routes are: matching routes connecting two regions, partial routes from either or both regions, or no routes in both regions. In the first case (see Fig. 2), the planner selects a “best” matching case based on additional information about the cases such as total distance and number of path segments. With reference to Fig. 2a, three possible candidate routes are a, c, and d. Among these d would be chosen as it is shorter than others. However,

Figwe 2.

85

a complete route is not reused always. A corridor of predefined size between the start and goal points is considered and only the path segments that fall within this corridor of travel are reused. This would ensure that the reused route does not lead to too much of overhead in length. The diameter of the corridor (cylindrical shape) is a programmable variable (200 feet in the experiments illustrated in this paper). The second situation is when there are no complete routes connecting the start and end regions, but there are many path segments in both regions which lead in the desired directions. A set of path segments is selected from different routes evaluating the amount of repair needed to join them. By constructing a partial route from either start or end, the problem is reformulated to connect the new stranded end points. For example, as shown in Figs. 2b, a.5, a4, a3 and cl, c2 c3 are path segments that would be considered and one possible solution is to compose a route using c2, c3 from one end and a5, a4 from other end along with a new short segment n that connects these two partial paths. In the third situation in which no routes are available, a new route is synthesized considering the specific characteristics of the navigational and environmental parameters as described in the following section. The routes selected from the map database may require some extent of repair to meet the current specifications such as constructing entry and exit ramps to the selected route, synthesizing new path segments to take care of mismatches in maximum speed or maximum depth. For example, if the maximum depth at any point in the selected route exceeds the limit prescribed by the mission, corresponding segments are rerouted by deleting the old ones and connecting the stranded points in the route. If travel time is a constraining factor, certain path segments are straightened within the limits of maximum path length in order to reduce the total length. The new path segments needed for repairing the routes could be planned using the same approach of adaptation or synthesis.

Searching old routes.

11

86

7.

Vasudevan and Ganesan

Synthesis of New Routes

New routes need to be synthesized when no useful or adaptable routes are found in the database. Since the underwater environment is relatively less cluttered than land environment, it is possible to have simple lineof-sight paths as long as there are no obstacles in the path. As explained earlier, the requirement of position computation puts an upper limit to the length of each path segment. Normally, position correction is performed after completing each of the path segments. Even if a long straight path is available, it may have to be broken down into multiple segments in order to meet the requirement of correcting the vehicle position after traveling a specified distance. The interval of position correction is dependent on factors like the type of mission, the speed and depth of travel, speed and direction of water current, and vehicle parameters. A design case-library is used to store the episodic information of these parameter combinations and corresponding design decisions. Once the segment length and the maximum speed are determined, the next step is to generate the segment by computing the waypoint co-ordinates. Normally, a straight line path is planned if there are no obstacles along the path. The presence of obstacles is checked by a query to annotated map database to supply all objects on the given “corridor” of travel. The diameter of the corridor should be a function of the navigational error rate and the environmental conditions and in the current implementation, it has the same value as the segment length. If there are obstacles present in the straight line path, the path segment is rerouted to avoid them. The annotations available in the obstacle representation in the map provide information about the paths that help to go around them (see Fig. 3). The nearest waypoint is chosen to connect the segment from the start location, the waypoints are then traced around the obstacle, and finally, an exit is made from the waypoint closest to the destination point. Once one set of waypoints are fixed, the path planning algorithm is recursively applied either to compose or to synthesize from the new point to the destination. The complete route is output by appending different sets of segments represented as a sequence of waypoints. Figure 4 shows some sample routes synthesized by the system. The first route will hit two obstacles if a straight line path is designed. The annotations stored in the obstacles keep the path away from the obstacles. The second route is very similar to the first one.

12

Figure 3.

Paths around obstacles as annotations.

Figure 4.

Path planning-route

synthesis.

The third route will hit only one obstacle if a straight line path is designed. The annotation keeps it away from the obstacle. Note that the path goes towards the obstacle to the use the path around it. The length of the distance between two way points dictate to certain extent how close to the obstacle the path will go before using the annotation. Figure 5 shows a three dimensional plot of another example of a scenario in which there are two cylinder objects each with annotations providing information regarding how to go around the objects. The first cylinder has top center point (550 500 275), radius 25, and height 200. The second cylinder has top center point (825 500 125), radius 25, and height 200. A route is synthesized from point S (825 500 125) to point E (825 500 125).

Case-Based Planning for AUVs

/IPI

0

Figure 5.

Path planning-another

route synthesis

I...;. 0

Figure 6.

A straight line path segment with way points placed at equal intervals would hit both cylinders. The annotations help to bend the path upwards to avoid these cylindrical objects. The depth is always measured from water level. In the plot, the maximum z axis value (600) represents the water level and hence a point at depth 125 is shown at (600 - 125) = 475. The shape of the obstacles is not relevant as long as it has annotations to describe routes around them. The annotated map system that was used to test the planner does not support irregular shaped objects. However, it can support composite objects that can be used to describe an object of irregular shape by using more than one regular shaped (box, cylinder etc.) subobjects. Currently, the annotations around the objects should be computed and entered manually. An extension would be for providing automatic calculation of various ways to go around regular shaped obstacles. This feature should be provided by the annotated map so that the path planning system can make use of it. 8.

Implementation

and Results

The Annotated Map System and the Case-Based Path Planner are coded and tested. In addition to search, compose, and synthesis modules, the system has a learning module which updates the map by adding new routes generated. The map is pre-loaded with randomly placed obstacles (for testing purposes, all of them are circular in shape) with safe waypoints around them. With no routes present in the map, the path planner initially turns to synthesis and computes the waypoints and modifies the paths between them to avoid known obstacles.

200

/pa

.R./“6.. OUEZ 400

B\P

I iOUTE4 I 600 800

Path planning-route

87

. . . ... . 1000

1200

1400

., 4 1600

adaptation.

Figure 6 illustrates a reuse situation in which, the map was preloaded with two routes ROUTE-l and ROUTE-2. Using this map, a new route-ROUTE-3was planned. ROUTE-3 is made of path segment pl 1 which was synthesized, followed by reused path segments of ROUTE- 1 (p2 and p3), the new segments p 14 and ~15, the path segment pl 1 of ROUTE-2 and finally two new segments p16 and ~17. It can be noticed that a new path is generated partially by synthesis and partially using the old path segments of different neighboring routes. Similarly, ROUTE-4 is a new route planned partially using the segments of ROUTE-2 and synthesizing another set of new segments, ROUTE-3 and ROUTE-4 were stored in the annotated map database. The third route-ROUTE-5-generated by the planner uses p10 of ROUTE-2 (also of ROUTE-4) and p19 and p20 segments of ROUTE-4 in addition to the new segments ~23, ~24, ~25, ~26, and ~27. Thus, the latest route could make use of some path segments, previously generated by the planner itself. Reuse of old paths obviously improves the efficiency of path planning with certain overheads in travel distances. Table 5 presents some metrics of system performance. Figure 7 and Table 5 show results of another set of experiments where the routes pass through varying depths. The original map was loaded with two routesROUTE-6 and ROUTE-7. As shown in this figure, ROUTE-8 reuses several path segments of ROUTE-6. ROUTE-9 uses a couple of line segments of ROUTE-6 and the others are newly synthesized ones. No obstacles are shown in this map as the emphasis is on route adaptation. A third route, ROUTE-10, was generated by taking partial segments from both ROUTE-6 and 13

88

Vasudevanand Ganesan

Table 5.

Performance figures.

Route name

Straight dist. (in ft.)

Route-3

1421.6

Route length (in ft.) 1610.97

% of reuse 68

% of dist. overhead 13.3

Route-4

1726.27

1842.5

57.5

6.7

Route-5

1442.22

1635.15

48.5

13.4

Route-8

1833.7

1892.0

73.0

3.2

Route-9

1476.5

1752.2

42.6

18.7

Route-10

1523.2

1833.1

68.3

20.3

Figure 8.

Path planning-performance

measures.

Also shown in Fig. 8 is the time taken to plan routes as the casebase becomes richer and richer. The observed measures are very attractive in comparison with the path planning time reported by Liu et al. (1994) which are about 5 seconds and 10 seconds respectively for R-Finder and Dijkstra’s algorithm (actual size of map is not given).

9.

Figure7.

Path planning-another

ROUTE-7. The end segments are newly synthesized. Measurements of the routes and reuse and overhead metrics are also given in Table 5. If obstacles were to be included, then the synthesis part would consider their presence and use annotations stored in those obstacles if needed to plan the paths around them. In another performance test, the system was continuously run to plan about 80 routes, each time storing back the planned route if it is different from existing ones, The map was preloaded with four randomly placed obstacles with their safe waypoints around them. The start and end points are randomly selected within the map. The reuse and overhead metrics were computed. Figure 8 depicts the plot. of percentage of reuse and percentage of distance overhead as the routes are accumulated. It is interesting to note that while the reuse steadily increases to almost 80%, the distance overhead more or less stabilizes at 20%. This clearly illustrates that the gain from reusing the path segments is considerable. The advantage of reuse of past navigational paths would be more dominant when we plan very long routes of many thousands of feet. 14

Conclusions

route adaptation

We have presented the design and implementation of a case-based path planning system. The pIanner uses a spatial indexing of past route cases with the help of the annotated map database. Whenever, reusable path segments are not available in the database, new segments are synthesized. The performance evaluations indicate that the overheads in reusing old path segments is not considerable compared to the reuse factor. The time taken to plan routes is also considerably lower than similar work reported. The classical algorithmic approaches like A* has a major drawback that even when the same problem is given again and again, the time and effort needed to compute the sohrtion does not improve. In other words, these methods do not use its own past solutions and intermediate results for subsequent problems. CBR attempts to exploit this past experience as we humans often do. Also, the complexity of the problem does not grow as the area of map or length of route increases. Complexity of problem solving in this CBR approach arises from the search operations in the map which is not dependent on the area of map or length of routes. Storage spaceis indeed an issue. However, considering the real-time responses needed for on-line replanning

Case-Based Planning for AUVs

of routes during a mission, the extra memory requirements are admissible. Moreover, the specific design of the annotated map database has led to a memory efficient geographical repository. In this system implementation, new routes planned can be stored back in the casebase resulting in an incremental learning facility. With a rich set of old route plans, it is possible to simply look up the database to meet new requirements rather than computing from scratch. Another advantage that stems from this is the self documentation of routes planned for future reference and analysis. This path planning scheme, though, targeted for AUV missions, could be useful in other applications as well such as land navigation, message routing through communication networks, and commercial delivery vehicle routing.

89

Qiu, Kand Feng, X. 1991. Trajectory planning of underwater vehicle using dynamic CRP model. In Proc. of the 1991 Symposium on AUV Technology, pp. 1082-1086. Quinn, Andrew. W., and Lane, David M. 1994. Computational issues in motion planning for autonomous underwater vehicles with manipulators. In Proc. of the 1994 Symposium on Autonomous Underwater Vehicle Technology, Cambridge, Massachusetts, pp. 255-262. Vasudevan, C., Smith, S.M., and Ganesan, K. 1994. Fuzzy logic in case-based reasoning. In Proc. Joint Conference of NAFIPS, IFIS, and NASA on Fuzzy Logic and Neural Networks, pp. 118-128. Warren, C.W. 1990. A technique for autonomous underwater vehicle route planning. IEEE Journal of Oceanic Engineering, 15(3): 199204.

References Caroll, K.P., McClaran, S.R., Nelson, E.L., Barnett, D.M., Friesen, D.K., and Williams, G.N. 1992. AUV path planning: An A* approach. In Proc. Symposium on AUV Technology (AUV 92), pp. 3-8. Chappel, ST. 1987. A blackboard based system for context sensitive mission planning in an autonomous vehicle. In Proc. Fifth International Symposium on Unmanned Untethered Submersible Technology (LUST 89), pp. 467-476. Chen, P. 1992. Improving path planning with learning. In Proc. of the 9th Int. Conference on Machine Learning, pp. 55-61. Ganesan, K., Dunn, S.E., Vasudevan, C., and Rae, G.J.S. 1992. Annotated maps for autonomous underwater vehicles. In Proc. 18th Meeting of the US/Japan Marine Facilities Panel of UJNR. Goel, A.K. and Callentine, T.J. 1992. An experience-based approach to navigational route planning. In Proc. IEEE/RS.IInt. Conference on Intelligent Robots and Systems, pp. 888-893. Haigh, K. and Veloso, M. 1993. Combining search and analogical reasoning in path planning from road maps. In Proc. of the Workshop on Case-Eased Reasoning, Washington D.C., pp. 79-85. Hammond, K.J. 1989. Proceedings of the DARPA Case-based Reasoning Workshop, Morgan Kaufmann Inc. Hwang, Y. and Ahuja, N. 1992. Gross motion planning-A survey. ACM Computing Surveys, 24(3):219-292. Kao, M., Weitzel, G., and Zheng X. 1992. A simple approach to planning and executing complex AUV missions. In Proc. of the Symposium of AUV-AUV-92, pp. 95-102. Kolodner, J.L. 1988. Proceedings of the DARPA Case-based Reasoning Workshop, Morgan Kaufmann Inc. Liu, B., Choo, S., Lok, S., Leong, S., Lee, S., Poon, F., and Tan, H. 1994. Integrating case-based reasoning, knowledge-based approach and Dijkstra algorithm for route finding. In Proc. of the IEEE Conference on AI Applications, pp. 149-155. Pouliot, M. and Smith, J.T. 1992. Integrated mission planning architectures for unmanned underwater vehicles. In Proc. of the 1992 Symposium on Autonomous Underwater Vehicle Technology, Washington DC., pp. 85-90.

C. Vasudevan received the B.Sc. (Engg.) degree with Honors in Electronics Engineering from University of Kerala, India in 1976, the M. Tech. degree in Electrical Engineering from Indian Institute of Technology, Madras, India in 1978, and the Ph.D. degree in Computer Science from Florida Atlantic University, in 1995. From 1978-1991, he served as Project Engineer and Member Technical Staff at Electronics R&D Centre, Govt. of India, Trivandrum. He is currently working as Software Engineer at Sun Light Technology, NJ. Vasudevan is a Senior Member of IEEE and Member of Phi Kappa Phi.

K. Ganesan received the B.Sc. and MSc. degrees in Statistics from Loyola College of Madras, India and Indian Institute of Statistics of Calcutta, India, in 1980 and 1982, respectively. He then studied at Indian Institute of Technology of Madras, India and received the M.S. degree in Computer Science in 1984. He received his Ph.D. degree in Computer Science from Boston University, Boston in 1989. Dr. Ganesan is currently an Associate Professor of Computer Science and Engineering at Florida Atlantic University. He is an active participant in the AUV development program of the Ocean Engineering Department at Florida Atlantic University. His research interests include autonomous robots, artificial intelligence, algorithms, and complexity theory. He is a member of ACM, IEEE, and Upsilon Pi Epsilon.

15