Exhaustive Grid Search Algorithm

This algorithm works by gridding up a space and then checking all valid move locations from a given starting point and adding them to a list. It then iterates through the list checking valid moves and creating a new list. This continues in an expanding fashion until the goal location is reached. Some basic optimization has been included to prevent rechecking of spaces. The overall algorithm is basically a wave-front planner done in Mathematica.

Grid Search Source Code

Basic without obstacles Obstacles with unsafe boundary checking
Obstacles with safe boundary checking

Controllability and Path Finding

Mathematica code was used to generate the constraints of motion and the controllability matrix describing the motion of a rolling disk, the kinematic car, and the segway constrained systems. To determine the controllability matrix, the body velocity and necessary transform matrices were calculated. The constraints matrix was then determined, and the null space used to find the distribution matrix. The controllability matrix was then calculated using Lie brackets.

Since the rolling disk is controllable, a basic path can be found for the disk to travel from a start location to a goal location while avoiding obstacles. A wave-front planner determines a path and then, using Euler rotation matrices, the program animates the motion of the disk along the path chosen by the planner.

The rolling disk below has dynamics described by Euler-Lagrange equations and a constraints matrix. As a result it rolls around a circular path.

Controllability Source Code
Path Finding Animation Source Code
Constrained Rolling Disk Source Code

Disk Motion and Path Finding
Constrained Rolling Disk

Probability Road Map and Constraints

A probability road map (PRM) is a probabilistic method for quickly determining a path. The algorithm chooses N random safe points and then makes connections to the K nearest neighbors. It's then possible to use many algorithms to compute a chain from a start point to an end point. This code implements a tree search style algorithm to compute a shortest hop path.

PRM Source Code

PRM Animation


This project used mathematica to simulate the dynamics of dock crane. A PRM was used to determine a path for the crane and a basic PD controller to drive the crane along the path. This project used Euler-Lagrange equations, body velocity matrices, inertial matrices, and Euler rotation matrices. The cranes cable was simulated as N rigid links connected with ball joints and to limit computational complexity N=2 or 3 was used. Because the system for the swinging crane is non-linear, the system was linearized which provided good results at slow enough speeds, but was unstable as the driving forces for the controller were increased.

Project Source Code
Summary and Conclusion

Controlled - 200 sec
Badly Controlled - 50 sec
Animation with collision
Animation with different box characteristics

Valid CSS      Valid XHTML