Path Planning

• This is a minimisation problem

• Example: the Travelling Salesman Problem

• also known as Hamiltonian Path

• Given n cities, what is the shortest route to each city, visiting each city exactly once

• Want to minimise total distance travelled

• Also must obey the “Visit Once” constraint