SIMPLE PATH-PLANNING ALGORITHM FOR MOBILE ROBOTS USING QUADTREES

摘要

The paper presents a simple path-planning algorithm that selects a reasonable collision-free path tying start and goal points and using a quadtree representation of the robot workspace. A new method for neighbor finding in binary images, which combines two forms of quadtree representation - matrix and linear quadtrees, is used in a path planning procedure in which the obstacle regions and further every free region smaller than the robot sizes are regarded as forbidden regions. The sequence of free region quadrants includes at least a collision-free path of the mobile robot by connecting all center points in every edge where the free regions are close each other. More illustrative examples are included.