Ändringar mellan två versioner
Här visas ändringar i "Assignment 2 " mellan 2015-03-12 09:54 av Petter Ögren och 2015-03-12 09:57 av Petter Ögren.
Visa < föregående | nästa > ändring.
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. (Ignore possible collisions in this task)
* 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). Assume that the vehicles occupy circular discs with radii R.
* 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. Also include discussion of performance relative to other groups (info from wiki-page and presentations).
* 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 (ignoring the destinations) using the dynamic point mass (amax=1)
* P2: Use the environment above to solve T5 (ignoring the customers) using the dynamic point mass (amax=1)
* P3: Use the environment above to solve T3 using the dynamic car (amax=1, phimax=1)
* P4: Use the environment above to solve T5 using the dynamic car (amax=1, phimax=1)
An empty background, with starting and end positions, can be found in this file polygObst2.mat,
which can be plotted using plotPolygObst2.m. The environment can be seen here polygonalMap2.pdf
(the lines connecting start and end points indicate who goes where).
* P5: Use the environment above to solve T4 using the dynamic point mass (amax=1)
Two discrete maps, including starting, ending and customer positions, can be found in these files discObst1.mat , discObst2.mat, which can be plotted using plotDiscObst1.m and plotDiscObst2.m. The corresponding maps can be seen here map1.pdf, map2.pdf.
* P56: Use the environment in discObst1.mat to solve T1
* P67: Use the environment in discObst1.mat to solve T2
* P78: Use the environment in discObst2.mat to solve T1
* P89: Use the environment in discObst2.mat to solve T2
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)
* Proportional Navigation (for min time intercept, reverse for collision avoidance) (link)