Pathfinder with A*

Repository

Introduction

Exploration robots are able move in complex environtments using its censors to detect and avoid obstacles and find good paths towards its goal. For this matter, during my Robotic Manipulation class we studied different kinds of pathfinder alghorithms. Being A* the most popular of them, our final assignment consisted on a Python implementation of it aiming to find the best route in a graph, composed by nodes where a robot could follow in a straight line without a collision. In addition in order to test my A* alghotithm, I also implemented a dynamic version of it using the Pygame library to build a dynamic interface so the alghoritm’s execution can be seen in real time.

Real Time A*

The real time A* is not only a neat way to see the execution of the A* module but also a good way to see if it is working the way I desired. As said before this interface uses the Pygame library and in order to make it work a start point and end point (obstacles are optional) need to be input. The box bellow shows the keys instructions:

A* Demo from MSR at Northwestern on Vimeo.

Live_aStar_Legend

Graph Path Finder

For this approach, given a graph composed by an N number of nodes where a route is a straight line between each node, the alghorithm will try to compute the sequence of routes it will take a starting node to an end node. Although, it will not consider rotes that goes through or collide with an obstacle (the robot will have a radius).

The following steps will be taken on when the path finder script is executed:

Image of a legend