RoverSim AIs

Random

The Random AI was the original AI the project started with, and its only purpose was to demonstrate how to control the rover. Each step it first collects, processes, and transmits a sample, then decides to go in a random direction, after which it collects power. This process is extremely inefficient, and it invariably runs out of power almost immediately.

Intelligent Random

The Intelligent Random AI is my first improvement over the Random AI. It intelligently rations its power and collects, processes, and transmits samples efficiently. When moving it will always choose an adjacent unsampled smooth tile if available. Only when it isn't next to an unsampled smooth tile will it move in a random direction. These changes result in a substantial increase in the number of samples sent over the original AI.

Mark I

The Mark I AI is very similar to the Intelligent Random AI, as the handling of non-movement actions is identical. Likewise, it also prioritizes unsampled smooth tiles when adjacent to them. However, it differs in that it keeps moving in its previous direction, and attempts to detect when it is stuck and tries to escape. This often results in many more samples collected than before. Unfortunately, the small amount of memory it has means that it isn't very good at detecting when it is stuck, or how to escape once it is stuck. This means that in many situations, it's trapped in a loop and bounces between walls until it runs out of moves or power.

So in the optimal case it can do very well:

And in the worst case, rather poorly:

Mark II

The Mark II AI is the most advanced of the 4 AI. It features more efficient power management such as logic for low power and low moves. It will also (ab)use the No Backtrack mechanic to gather enough power for the rest of its moves. The most important change, however, is in the movement logic. While moving, the rover will create a map of all of the surrounding terrain. The rover will then use Dijkstra's algorithm to find a path to the closest unsampled smooth terrain on the map. The path finding algorithm means that the rover will never get stuck in a corner like the Mark I is prone to.

You might notice that the Mark II does have a tendency to stay in areas of the map that have already been mostly sampled. This might be fixed by weighting groups of unsampled or unknown tiles higher to convince the rover to travel to unsampled areas.

Limited State AI

The Limited State AI can be thought as the next iteration of the Mark I. It has a more advanced obstacle avoidance algorithm, and remembers up to 5 dead ends to avoid. These improvements mean the rover can almost always find its way out of a corner and very rarely gets stuck. As a result, the Limited State AI sends almost as many samples as the Mark II on average, while at the same time requiring considerably less processing power and keeping just a small, fixed amount of memory. In addition, it is almost as consistent as the Mark II.

Pathfinding AI

The Pathfinding AI combines the terrain mapping and navigation abilities of Mark II with the intelligent power gathering of the Limited State AI and improves on them even further. It does this by splitting its operation into several phases and subphases:

1. Power Gathering - Collects the power the rover needs for the rest of the run
   1. Exploration - Finds an area that can be used to gather power
   2. Exploitation - Drives up the No Backtrack counter until enough power is gathered
2. Collection - Collects and processes samples using Dijkstra's algorithm to find the nearst unsampled tiles
3. Low Moves - Transmits the processed samples, collecting and processing few last samples if possible

During the power gathering phase, the AI also has special logic to ensure it doesn't run out of power before it can gather enough power to become self sufficient. Since Collect Power will always yield at least one power, any time the rover is about to run out of power, it repeatedly calls Collect Power until it has enough power to do the next action. This burns a lot of the action budget, but it's a better than running out of power altogether. In fact, over 10 million unique simulations, the rover did not fail once.

The collection phase drops the use of round robin, as pathfinding means that the rover always knows where the nearest unsampled tile is. Nor does it prefer smooth tiles over rough tiles, since the Power Gathering phase provides enough power to gather either. The consistent path means that less time is wasted moving over sampled tiles, increasing total sample count.

Statistics

Each AI was run 2,000,000 times and the results tabulated:

Something you might notice from the data is that while the Mark I is on average slightly better than the Intelligent Random AI, it has a much higher variance, due to its tendency to get stuck in corners.

Note that the Mark II, while having one of the highest rate of samples sent, also takes significantly longer to simulate! This is due to the unoptimized path finding algorithm, as it runs almost every step. The other AI have much less complex logic, and are measured on the order of nanoseconds.