Guidelines

This is a programming assignment. You will be provided sample inputs and outputs $($see below$).$

The goal of the samples is to check that you can correctly parse the problem definitions and

generate a correctly formatted output which is also a correct solution to the problem. For

grading, your program will be tested on a different set of samples. It should not be assumed that if your program works on the samples it will work on all test cases, so you should focus on making sure that your algorithm is general and algorithmically correct. You are encouraged to try your own test cases to check how your program would behave in some corner cases that you might think of$.$ Since each homework is checked via an automated A$.$I. script, your output should match the specified format exactly. Failure to do so will most certainly cost some points. The output format is simple and examples are provided below. You should upload and test your code on vocareum.com, and you will also submit it there.

Project description

In this project, we look at the problem of path planning in a different way just to give you the

opportunity to deepen your understanding of search algorithms and modify search techniques

to fit the criteria of a realistic problem. To give you a context for how search algorithms can be

utilized, we invite you Mars. Using a rover, we want to collect soil samples. Because the rover

has a limited life expectancy, we want to travel from our current location to the next soil

sample location as efficiently as possible, i$.$e$.,$ taking the shortest path. Using advanced satellite

imaging techniques, the terrain of Mars has already been scanned, discretized, and simplified

into a set of locations that are deemed safe for the rover, as well as a set of path segments that

are safe between locations. This is similar to a standard route planning problem using a

topological map of cities and street segments, except that here we also account for elevation

$($locations have $3$D coordinates$).$ One additional complication is that the rover has a limited

amount of available motor energy on every move, such that it cannot travel on path segments

that are going uphill above a certain limit$.$ This, however, can be overcome in some cases if the

rover has gained some momentum by going downhill just before it goes uphill. This is explained

in more details below. For now, just beware that whether the rover can or cannot traverse an

uphill path segment depends on whether it has been going downhill and has gained momentum

just before.

Search for the optimal paths

Our task is to lead the rover from a start location to a new location for the next soil sample. We

want to find a shortest path among the safe paths, i$.$e$.,$ one that minimizes the total distance

traveled. There may be one, several, or no solutions on a given instance of the problem. When

several optimal $($shortest$)$ solutions exist, your algorithm can return any of those.

Problem definition details

You will write a program that will take an input file that describes the terrain $($lists of safe

locations and of safe path segments$),$ the starting location, the goal location, and the available

motor energy for going uphill. Your program should then output a shortest path as a list of

locations traversed, or FAIL if no path could be found. A path is composed of a sequence of

elementary moves. Each elementary move consists of moving the rover from its current safe

location to a new safe location that is directly connected to the current location by a single safe

path segment. To find the solution you will use the following algorithms:

$-$ Breadth$-$first search $($BFS$)$ with step cost of $1$ per elementary move.

In all cases, you should consider that a path segment is only traversable if either it is not going

uphill by more than the uphill energy limit$,$ or the rover currently has enough momentum from

the immediately preceding move to overcome that limit$.$

Terrain map

The terrain will be described as a graph, specified in input.txt using two lists:

$-$ List of safe locations, each with a name and a $3$D coordinate $($x$,$ y$,$ z$)$

$-$ List of safe path segments, each given as a pair of two safe location names.

Path segments are not directed, i$.$e$.,$ if segment $$aaa bbb$$ is in the list, then the rover could in

principle either travel from aaa to bbb or from bbb to aaa. Beware, however, that the uphill

energy limit and momentum may prevent some of those travels $($details below$).$

To avoid potential issues with rounding errors, your path will be considered a correct solution if

its length is within $0\mathrm{.}1$ of the optimal path length calculated by our reference algorithm $($and if it

also does not violate any energy$/$momentum rules$).$ We recommend using double $(64-$bit$)$ rather than float $(32-$bit$)$ for your internal calculations.

Energy and momentum

The required energy for a given move is always calculated from a point $($x$1,$ y$1,$ z$1)$ to another

point $($x$2,$ y$2,$ z$2)$ as z$2$ z$1.$