Optimal Control of Autonomous Rover

Inspiration

What it does

//The software we developed instructs a simulation of a small autonomous robot and a similar physical robot to arrive at randomly generated targets and avoid randomly generated obstacles. The robot is placed in an environment with significantly more targets than it could, given its slow speed, reach in the allotted time. Our algorithms are intended to optimize the performance of the robot during this time.

How we built it

//We developed three independent algorithms, each with relevant error adjustment features. One algorithm simply finds the point nearest to the position of the rover and targets this point. Another algorithm computes a score for each point on the map based on weighted two metrics, the sum of the distances to all other points and the proximity of the point to the rover's position. The algorithm directs the rover to the nearest and densest areas of the map based on this. The third algorithm bStarExtend is a task specific adaptation of an A* search. A* value function classically implement a two parameters:

Value(p) = d(p) + h(p)

With p the point under consideration With d the cumulative distance to get to p, h the distance approximation to get to p. The goal being to follow a path that minimize such value. It recursively expand a "frontier" of point, always picking the smallest value. In order to adapt the algorithm to the task we decided to adopt a model based approach and use time instead of distance to quantify the point value. To do so, we first built an approximate model of the rover speed, and angular speed based on the simulation and the data collected during the testing. Then we computed d(p) as the sum of the time necessary to turn toward the point and go to it in a straight line from the frontier point being extended. To approximate the distance to the task goal h(p), that was not as simple as going from point to point, we decided to use the approximate time it would take us to get all the available points in the vicinity if those were distributed evenly in the surface. Such a distribution led to an ideal distance to get all the points of :

Daverage = sqrt(1/q)*N.

With N the number of points in the area, and q the density of points q = (N*radius/S). The availability of point S, the surface around the point being extended, progressively got smaller with the time left the rover had to finish the task. Although we think this approach is interesting, further study of the algorithm behaviour would be necessary to perfect it.

If the rover does not find its target or strays from its intended path, the software identifies a new target for the

Challenges we ran into

//We did not begin to test with the physical rover until fairly late into the hackathon. We found the differences between the performance of the simulation and the performance of the physical rover to be significant. An inability to rely on some of the rover's basic sensors made the implementation of our solutions difficult, but nevertheless posed an interesting challenge.