Route finding by using knowledge about the road network
IEEE Transactions on Systems Man and Cybernetics - Part A Systems and HumansPublished 1 July 1997Open access
Bing Liu
Citations51
SJR quartileQ4
SJR score0.11
SNIP0.06
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This project has integrated knowledge-based technique and algorithmic method to solve the shortest path problem, and substantially reduces the computation time and space required for route finding.
Abstract
10.1109/3468.594911
Keywords
Computer Science
Building expert systems
1,699 Citations1983Frederick Hayes‐Roth, D. A. Waterman +1 more
Artificial Intelligence ReviewAn introduction to case-based reasoning
1,024 Citations1992Janet L. Kolodner
This paper discusses the processes involved in case-based reasoning and the tasks for which case- based reasoning is useful.
Cognitive ScienceModeling Spatial Knowledge*
742 Citations1978Benjamin Kuipers
The TOUR model captures the multiple representations that make up the cognitive map, the problem-solving strategies it uses, and the mechanisms for assimilating new information.
Studies in operational regional scienceRoute Choice: Wayfinding in Transport Networks
344 Citations1990Piet H. L. Bovy, Eliahu Stern
Artificial IntelligenceQualitative navigation for mobile robots
331 Citations1990Tod S. Levitt, Daryl T. Lawton
This work has developed a multi-level theory of spatial representation of the environment based upon the observation and re-acquisition of distinctive visual events, i.e., landmarks, that provides the theoretical foundations for a visual memory database that smoothly integrates available metric knowledge of relative or absolute angles and distances.
Mathematics of ComputationLinear Network Optimization: Algorithms and Codes.
323 Citations1993Donald K. Wagner, Dimitri P. Bertsekas
NetworksShortest‐path algorithms: Taxonomy and annotation
311 Citations1984Narsingh Deo, C. Y. Pang
A classification scheme to characterize algorithms for solving shortestpath problems is evolved and a more complete listing of 222 references carefully culled out of a larger body of literature on shortest-path algorithms through the year 1979 is provided.
Management ScienceOn the Shortest Route Through a Network
226 Citations1960George B. Dantzig
This paper refines proposals to give what is believed to be the shortest procedure for finding the shortest route when it is little effort to arrange distances in increasing order by nodes or to skip consideration of arcs into nodes whose shortest route to the origin has been determined earlier in the computation.
NetworksA computational analysis of alternative algorithms and labeling techniques for finding shortest path trees
224 Citations1979Roman Dial, Fred Glover +2 more
The study shows that the procedures examined indeed exert a powerful influence on solution efficiency, with the identity of the best dependent upon the topology of the network and the range of the arc distance coefficients.
The Computer JournalFinding the Shortest Route between Two Points in a Network
161 Citations1966Tony Nicholson
A new method is proposed for finding the shortest route between two points in an interconnected network by investigating a selection of routes from both the starting point and the terminal point.
Artificial IntelligencePlanning routes through uncertain territory
159 Citations1984Drew McDermott, Ernest Davis
A partial solution to the problem of constructing a fuzzy map is presented, an algorithm that assimilates a fact first by imposing constraints on the fuzzy coordinates of the objects involved, then by rearranging or growing the tree of frames of reference.
Mathematical programming studiesShortest path methods: A unifying approach
149 Citations1986Giorgio Gallo, Stefano Pallottino
This analysis suggests a new classification of the shortest path algorithms, showing all the algorithms described to derive from one single prototype method, the difference between them depending only on the particular data structure used in their implementation.
International Journal of E-Entrepreneurship and InnovationArtificial Intelligence
86 Citations2018Christina McDowell Marinchak, Edward Forrest +1 more
The authors will address the single most defining phenomenon that is affecting the marketer's role and function in the marketing process: the exponential increase in the number, variety and capability of marketing applications, platforms and services that perform, control, influence and/or integrate virtually every marketing task and decision.
Lecture notes in computer scienceRoute planning by analogy
58 Citations1995Karen Zita Haigh, Manuela Veloso
This paper demonstrates the route planning method which retrieves and reuses multiple past routing cases that collectively form a good basis for generating a new routing plan and presents the similarity metric, which effectively takes into account the geometric and continuous-valued characteristics of a city map.
IEEE ExpertMultistrategy adaptive path planning
51 Citations1994Ashok K. Goel, K.S. Ail +3 more
The goal is to describe the general framework of multistrategy adaptive path planning, and the specific design of the Router system, and report on a series of experiments with Router in simulated navigation worlds.
Transportation Research Record Journal of the Transportation Research BoardEXCESS TRAVEL: CAUSES, EXTENT, AND CONSEQUENCES
41 Citations1987Gerhart F King, Truman M. Mast
NetworksLevel graphs and approximate shortest path algorithms
39 Citations1992Jacob Shapiro, Jerry Waxman +1 more
It is shown that the length of the path produced by LGS converges rapidly to that of the actual shortest path as the distance between the points increases.
Computational Optimization and ApplicationsThe one-to-one shortest-path problem: An empirical analysis with the two-tree Dijkstra algorithm
37 Citations1993Richard V. Helgason, Jeffery L. Kennington +1 more
The new algorithm, S22, combines the highly effective data structure of the S2 algorithm of Dial et al., with the idea of simultaneously building shortest-path trees from both source and sink nodes, and was found to be the fastest sequential shortest- path algorithm.
Representation, organization, and use of topographic models of physical spaces for route planning
27 Citations2002Ashok K. Goel, Todd J. Callantine +2 more
ROUTER 1 uses knowledge of the relative direction as a heuristic for selecting pathways and progressively adds more details to the growing route until a complete legal route is synthesized.
IEEE ExpertFinding the shortest route using cases, knowledge, and Djikstra's algorithm
26 Citations1994Bing Liu, Siew-Hwee Choo +5 more
This prototype system integrates Dijkstra's algorithm with knowledge-based and case-based components, reducing the time required to find the shortest path between points in a road network.
ComputingA parallel shortest path algorithm
20 Citations1988Th. Mohr, C. Pasche
A new algorithm to find the shortest path between a pair of nodes is presented that expands the search from origin and destination simultaneously, on the other hand it uses a lower bound for the shortest route to guide this search.
Integrating case-based reasoning, knowledge-based approach and Dijkstra algorithm for route finding
17 Citations2002Bing Liu, Siew-Hwee Choo +5 more
With this integration, knowledge about the geographical information and past cases are used to help Dijkstra's algorithm in finding a solution and this approach dramatically reduces the computation time required for route finding.
Using knowledge to isolate search in route finding
15 Citations1995Bing Liu
This paper presents an approach that uses knowledge about the road network to substantially reduce the time and space required in computation, and to ensure human oriented solutions, and three alternative methods are proposed, which may be used in different situations.