The travelling salesman problem
Introduction
The travelling salesman problem is a legendary math problem. The question is, how to find the shortest path to visit all the given cities and to come back home. To make the game interesting, many cities are needed, and thus a rather large floor area.
Aim
Distance, time. Geography.
Robot
Almost any robot will do, though we use Asimov 2/ Verne robot.
Sensors
No sensors are used, except the servo motors.
Example Video
Theory
Write (or print) the names of cities (eg. European capitals) into papers. The Wikipedia page includes 50 countries, and that might be too much, but choose 7 to 15 cities to be distributed and taped onto the floor.
Using only green steering blocks, try to visit as many cities as possible, and minimizing the travel distance or travelling time.
Example Code
The following code visits three Capitals but does not return home after the trip. In the beginning, the motor rotation is reset such that the total rotation of motor B can read from the program, see the red arrow.
Exercises
- Visit 10 cities. Note that after visiting multiple cities, the orientation of robot becomes wobbly.
- Print the total distance (of motor B) onto screen.
- Use gyroscope the fix the uncertainty with the direction.
- Try to minimize the time used to travel all the cities. Print the elapsed time onto screen.
Back to Mahtavaa Matematiikkaa 2020
