Visa version
Version skapad av Petter Ögren 2015-02-18 00:02
Visa
< föregående
|
nästa >
Jämför
< föregående
|
nästa >
Assignment 2
In this assignment, you will solve problems involving multiple agents.
- T1 (MTSP in a Maze): Given a discrete map, as in Assignment 1, starting positions of N vehicles and M customers, find paths for all N vehicles such that all M customers are visitied in (approximately) minimum time. Note that the vehicles must avoid collisions, i.e. they cannot pass through each other, or enter the same position at the same time.
- T2 (MTSP in polygonal map): Given a polygonal map, as in Assignment 1, starting positions of N vehicles and M customers, find paths for all N vehicles such that all M customers are visited in (approximately) minimum time. Assume that the vehicles occupy circular discs with radii R.
- T3: (Obstacle avoidance in empty space) Given an empty space, N vehicle starting positions, and a given destination for each vehicle. Solve the problem of reaching that destination without colliding with the other vehicles. Solve the problem in a decentralized manner (i.e. each vehicle has no knowledge of the starting positions or destinations of the others).
- T4: (mini Darpa Urban Challenge) Solve the same problem as above in a polygonal environment.
- T5: Implement the 3 different formation keeping algorithms (virtual structure, leader following and local interaction) using the kinematic point model
- T6: Implement the 3 different formation keeping algorithms for all motion models, by controlling each vehicle towards a point, the motion of which is given by T5 above.
- T7: Report in the form of a scientific paper.
- T8: Be ready to show your solutions at the final meeting.
Planning and Progress reporting
Same as in Assignment 1. Use the wiki-pages.
Links
- Cooperative Pathfinding, David Silver (http://www0.cs.ucl.ac.uk/staff/D.Silver/web/Applications_files/coop-path-AIWisdom.pdf)
- Obstacle Avoidance in Formation (link)
- A Control Scheme for Improving Multi-Vehicle Foration Maneuvers (link)
- Cooperative Control of Mobile Sensor Networks: Adaptive Gradient Climbing in a Distributed Environment (link)
- Behavior-based formation control for multirobot teams (link)
-
P. Toth and D. Vigo, “The Granular Tabu Search and Its Application to the Vehicle-Routing Problem,” INFORMS Journal on Computing, vol. 15, no. 4, pp. 333–346, Dec. 2003. (sorry, no link)
- Solving the Vehicle Routing Problem with Genetic Algorithms, Áslaug Sóley Bjarnadóttir (link)