Browse Prior Art Database

A TIME-CONSTRAINED ROUTE-PLANNING SYSTEM

IP.com Disclosure Number: IPCOM000006982D
Original Publication Date: 1993-Jun-01
Included in the Prior Art Database: 2002-Feb-14
Document File: 3 page(s) / 383K

Publishing Venue

Motorola

Related People

Yilin Zhao: AUTHOR [+3]

Abstract

Present route-planning systems still use static plan- ning to avoid the problems of dynamic time constraints imposed during the journey, i.e., they plan the route before the actual trip starts. In other words, users must wait patiently for an unknown period of time for the system to fmish planning. Planning a route based on an arbi- trary time period can no longer satisfy the market. This type of time-constraints especially applies to the in-vehicle embedded route-planning systems.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 50% of the total text.

Page 1 of 3

MOTOROLA INC. Technical Developments Volume 19 June 1993

A TIME-CONSTRAINED ROUTE-PLANNING SYSTEM

by Yilin Zhao, Laura Link and L. Gabor Seymour

1.0 PROBLEM STATEMENT

  Present route-planning systems still use static plan- ning to avoid the problems of dynamic time constraints imposed during the journey, i.e., they plan the route before the actual trip starts. In other words, users must wait patiently for an unknown period of time for the system to fmish planning. Planning a route based on an arbi- trary time period can no longer satisfy the market. This type of time-constraints especially applies to the in-vehicle embedded route-planning systems.

  There is a trade-off between the selection of the cost coefftcient and the search time and quality. For instance, from Figure 1 we can see that changing the cost coeffi- cient can improve the quality of the route generated by the system, in this case, reducing the number of maneu- ver turns and the travel time. However, the system must spend more time on planning. Therefore, such currently known systems suffer from a

* long planning time for a long trip, and * non-optimal (or sub-optimal) route for a short trip.

2.0 DESCRIPTION

  Based on the idea proposed in [5], a dynamic plan- ning system is described. In addition to travel distance, travel time and maneuver counts, this system uses the available planning time, map density and CPU load to guide the search process for finding the desired route.

  This system uses special cost-factor changes to restrict dynamically the search space of route planning. Usually, travel distance, travel time and maneuver counts are used as criteria for determining the route. For this new system, an initial search tree pruning coefftcient (C-prune) is selected at the start of route planning, depending on the distance between the start and desti- nation points. This coefftcient,is a cost difference thresh- old value between the cost of the alternative routes. Note that the coefficient may have different definitions for dii- ferent search algorithms. Only those route alternatives

152

will be selected that provide a cost improvement beyond this selected pruning coefficient. Thrs nnttal pruning coef- ticient value is expected to guarantee an upper limit to the route planning time assuming a certain node density in the area of the trip. In the course of route planning, when the speedy of route planning (V-m, the node density (N-RP) and/or the available CPU cycles (T-CPU change from the anticipated values, the search tree pruning coefficient is adjusted to provide an opti- mal route within the allowed route-planning time limit.

  A simple example of e...