A NEW PREPROCESSING TECHNIQUE IN CASE OF TINY OBSTACLES FOR VISIBILITY GRAPH-BASED PATH PLANNING
Path planning has applied in many fields such as bioinformatics, CAD/CAM, layout, image processing and especially in robotics. Its target is to find out the best path with respect to some optimization criteria in order that an object can move along the path from a starting point to an ending point in two or higher dimension spaces avoiding a set of obstacles. Path planning mainly follows three approaches: searchbased, sampling-based and combinatorial planning. In combinatorial planning, building a visibility graph is a main phase in the whole process and theoretically it takes O(nlogn).However, with some practical applications, for example one which has a large number of obstacles, this phase is very timeconsuming. This paper describes a simple and efficient preprocessing technique to reduce computation time when applying the visibility graph approach for path planning in case of many tiny obstacles. With a large set of randomly generated test problems, the experiment result shows that the computation time gets approximately a reduction factor of one-third.
Path planning visibility graph obstacle shortest path
TRAN THI NHU NGUYET RAN VAN HOAI
Faculty of Computer Engineering,University of Information Technology,VNU-HCM Faculty of Computer Science and Engineering, Ho Chi Minh City University of Technology, VNU-HCM
国际会议
3rd International Conference on Mechanical and Electrical Technology(ICMET2011) (2011第三届机械与电气技术国际会议)
大连
英文
431-439
2011-08-26（万方平台首次上网日期，不代表论文的发表时间）