DocumentCode :
1127103
Title :
Symbolic and geometric connectivity graph methods for route planning in digitized maps
Author :
Holmes, Peter D. ; Jungert, Erland R A
Author_Institution :
Nat. Defence Res. Establ., Linkoping, Sweden
Volume :
14
Issue :
5
fYear :
1992
fDate :
5/1/1992 12:00:00 AM
Firstpage :
549
Lastpage :
565
Abstract :
The results of research involving spatial reasoning within digitized maps are reported, focusing on techniques for 2D route planning in the presence of obstacles. Two alternative approaches to route planning are discussed, one involving heuristic symbolic processing and the other employing geometric calculations. Both techniques employ A* search over a connectivity graph. The geometric system produces a simple list of coordinate positions, whereas the symbolic system generates a symbolic description of the planned route. The symbolic system achieves this capability through the use of inference rules that can analyze and classify spatial relationships within the connectivity graph. The geometric method calculates an exact path from the connectivity information in the graph. Thus, the connectivity graph acts both as a knowledge structure on which spatial reasoning can be performed and as a data structure supporting geometrical calculations. An extension of the methodology that exploits a hierarchical data structure is described
Keywords :
computational geometry; graph theory; heuristic programming; planning (artificial intelligence); search problems; spatial reasoning; symbol manipulation; 2D route planning; A* search; digitized maps; geometric connectivity graph methods; heuristic symbolic processing; hierarchical data structure; inference rules; knowledge structure; obstacle avoidance; route planning; spatial reasoning; symbolic connectivity; Data structures; Feedback; Mobile robots; Path planning; Process planning; Remotely operated vehicles; Robot kinematics; Robot sensing systems; Sensor systems; Vehicle dynamics;
fLanguage :
English
Journal_Title :
Pattern Analysis and Machine Intelligence, IEEE Transactions on
Publisher :
ieee
ISSN :
0162-8828
Type :
jour
DOI :
10.1109/34.134059
Filename :
134059
Link To Document :
بازگشت