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 T6 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)

Example problems

A polygonal background, including starting, ending and customer positions. Can be found in this file polygObst.mat, which can be plotted using plotPolygObst.m. The environment can be seen here map.pdf (the lines connecting start and end points indicate who goes where).

• P1: Use the environment above to solve T3 using the dynamic point mass
• P2: Use the environment above to solve T5 using the dynamic point mass
• P3: Use the environment above to solve T5 using the dynamic car
• P4: Use the environment above to solve T5 using the dynamic car

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)