DocumentCode :
3356577
Title :
Finding the lowest-cost path for searching the grid-based environment
Author :
Gao, Bo ; Xu, Demin ; Zhang, Fubin ; Yao, Yao
Author_Institution :
Coll. of Marine, Northwestern Polytech. Univ., Xi´´an, China
fYear :
2009
fDate :
9-12 Aug. 2009
Firstpage :
593
Lastpage :
598
Abstract :
Searching the unknown or partially known region or acquiring the new information in the map is an important mission for vehicle in the areas of military and civilian use. Planning the lowest-cost path is one of the primary work for searching the environment. This paper develops a planning strategy which could minimize the cost and every corner in the map can be seen on the path based on cell decomposition. It firstly draws out the polygon structure from the environment based on grids. With the decomposition of polygon into triangulations, the method makes use of the watchman algorithm and builds the hourglass to construct the heuristics function for vehicle. Directed by heuristics and changing the search direction on essential cuts, the grid-based searching method finally gets our desired route through a so called mirror reflection. Throughout the simulation, such a method could make the optimal route and environment is visible on path. Compared with the path connected from random nearest neighbor points on essential line, our generated path is lower in cost.
Keywords :
computational geometry; minimisation; path planning; vehicles; cell decomposition; cost minimization; grid-based environment; grid-based searching method; heuristics function; lowest-cost path; map; mirror reflection; optimal route; planning strategy; polygon structure; random nearest neighbor points; triangulations; watchman algorithm; Automation; Cost function; Educational institutions; Mechatronics; Mirrors; Nearest neighbor searches; Path planning; Reflection; Skeleton; Space vehicles; hourglass; mirror reflection; path planning; watchman;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Mechatronics and Automation, 2009. ICMA 2009. International Conference on
Conference_Location :
Changchun
Print_ISBN :
978-1-4244-2692-8
Electronic_ISBN :
978-1-4244-2693-5
Type :
conf
DOI :
10.1109/ICMA.2009.5245056
Filename :
5245056
Link To Document :
بازگشت