Collecting Robots is a little project I have made as a project for a university course of Operating System for Robotics. The goal is to plan a strategy for some “robots” to collect some “objects” and taking them to some “collect points”. The robots also have a maximum capacity, i.e. they can take a maximum number of objects at once, so to go on they will need to take the objects to a collect point.
The problem is quite hard (I believe it is NP-hard) so my first thought was to use an heuristic approach. I implemented a genetic solution using the JSGenetic library I wrote some time ago.
Actually there’s a little problem with my implementation: the crossover operation is quite weak. It does not combine the two parent individual in a complete way, thus the generated children is often very similar to the parents. This moves the evolution capability towards the mutation process, which is much more random, and this means the evolution will lead more likely to a local optima. This is especially evident with large problems (many objects) when object positions are not uniformely distributed in the map.
The app is publicly available here.
Browser compatibility:
- [Google Chrome/Chromium] OK
- [Firefox] Some problems, “go” and “animate” button works but label doesn’t refresh (isn’t .innerText standard?), simulation is slower
- [IE] Not tested
- [Safari] Not tested
Some notes on usage of the app:
Map generation
You may use the randomly generated map which is presented on startup, generate a new one with the “randomize” button, or generate your own map.
To generate your map, just press “clear” to clear current map, then select the proper point you want to place on the dropdown list, and place it clicking on the map.
If you want to change the number of points used by the randomize option, you can place the point manually on the map, in the number and type you want them to be, and then pressing “randomize” will make a new random map with the number and type of points you placed.
Evolution of the solution
When the map is ready, you can press “init Evolver” to initialize the Evolver object, which is responsible for managing the evolution process.
Then, pressing “go” will start the evolution, showing the best solution found in the left canvas.
When you’re happy with the shown solution, press “stop”.
Simulation
Beware that you need to stop the evolution to run the simulation. Doing otherwise will lead to unknown results 😛
When you have a solution (you need to at least have initialized the Evolver), you can see the robots in action in the right canvas by pressing “animate”, which will start the simulation with the current solution.