QuadTree Path Finding Simulator

Mobile robots generally need to move from a START position (0) to a GOAL position (1) in order to accomplish tasks.

The simulator makes use of the Quad Tree method to create a distance graph and then this distance graph is used by the A* (A-star) path finding algorithm to find the best path.


Click on the map to create an obstacle (Pink square = obstacle, Green square = no obstacle)
Use the 'g' key to change the GOAL position
Use the 's' key to change the START position


The map's grid can be expanded to accommodate a larger map. For this simulation, however, it is fixed to an 8x8 array.

Although the Quad Tree method is applied using a grid, the robot can move freely around inside each grid and is not bound by the center point of any quad.

The numbers next to each Node ID is the values used by the A-star algorithm to determine the best path. The tutorial will follow soon explaining all the detail.


Particle Filter Localization Simulation

Let us assume the following: You want a robot that will fetch something from somewhere or should take something to someplace. In order for this mobile robot to know if it reached the goal, or to plan a path to the goal, it needs to know where it is.

This 'knowing where it is' is known as localization. One method used for localization is Particle Filters (Monte Carlo Localization) and this simulation implements particle filter localization.

The simulation consists of RED particles, a GREEN robot and BLUE landmarks (add landmarks by LEFT clicking on the map). By moving the robot around using the w,a,d keys you will see how the particles cluster around the robot, essentially showing where the robot is. (NOTE: If you do not add any landmarks the robot will not be able to localize.)