Assignment 2

In this assignment, you will solve problems involving multiple agents.

• T1: (Collision avoidance planning in a Maze) Given a discrete map, as in Assignment 1, starting and goal positions of N vehicles, find paths for all N vehicles such that the destinations are reached 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: (VRP 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.
• T3: (VRP 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.
• T4: (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/reactive manner (i.e. each vehicle has no knowledge of the starting positions or destinations of the others). 
• T5: (mini Darpa Urban Challenge) Solve the same problem as above in a polygonal environment.
• T6: Implement the 3 different formation keeping algorithms (virtual structure, leader following and local interaction) using the kinematic point model
• T7: 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.
• T8: Report in the form of a scientific paper.
• T9: Be ready to show your solutions at the final meeting.

Planning and Progress reporting

Very similar to Assignment 1. Use the wiki-pages (here)

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)