chipKIT® Development Platform

Inspired by Arduino™

Mapping/Path Planning

Created Thu, 01 Dec 2011 22:33:10 +0000 by Mr_Fixit


Thu, 01 Dec 2011 22:33:10 +0000

All, I have started making a library of tools to facilitate mapping, location tracking, and path planning. Its coming along very well, but during the development I realized that someone probably already has done this and might be willing to share. Below I describe what I have done so far, or wish to complete. The path planning routine needs the most work as the other modules are fairly polished.

So far, here is what I have: Location Tracking - This routine makes the initial assumption that the robot starts in location 0,0. Once the robot moves, the routine will calculate the direction and distance moved relative to last update and calculates the new X and Y position of the robot.

Mapping - When the sonar sensor or bump detectors find an object, the system will calculate the relative position of that object based on the current X/Y position and heading, and offsetting range when appropriate. It then logs the object in an array of objects it detects. The array grows by one each time. When logged, it checks to see if an object has already been detected there to avoid duplicates (Waste of memory). This method of mapping was chosen to make best use of limited memory.

Path Planning - There has been a few iterations of test development on this. The basic method emulates a stretching rubberband. Its basic operation follows a fairly standard wavefront search method to a point. It starts by searching for known objects starting at the current location to the destination (0,0). When an object is found, a waypoint is added, and the search branches from that point. When a new waypoint is added, the system does a straight line search from the new waypoint to the previous. When a straight line does not intersect a known object, waypoints in between are deleted, making best use of energy, memory, and time. The end result should be an array of potential paths. Those paths are then evaluated to determine shortest route. Once that is determined, all other paths are deleted. Following the path is straight forward until an unexpected object is detected, in which case the routine is started again from the new current position.


Fri, 02 Dec 2011 20:51:52 +0000

Are you familiar with SLAM?

Alan KM6VV