MAS A2 - Week 12

Group 2

Reza Hosseini & Robert Olsson Kihlborg

Planning

Final pieces of the puzzles falling into place

1. Read obstacle map (wrote my own version of this)
2. Read all groups of starts and goals
3. Calculate distances to all goals from all grid cells (Dijkstra heuristic)
4. Assign goals to starts (MDVR problem)
1. New solution! Greedy approach, penalize maximum distance and total distance
5. Calculate path for each vehicle
6. Calculate activity map, based on all paths
7. Recalculate paths, based on activities
• Added since last time. Iterate 5-6 for a number of times.
• A momentum parameter keeps a part of the old activity, to avoid oscillations.
8. Profit!

MDVR solution

• Greedy solution: add one goal at a time to the plan.
• How to choose goal?
• The goal that seems the most difficult to include should be prioritized
• Implementation is probably a bit bugged- the fourth goal should intuitively be placed between the third and the second goal

​

1

2

3

4

Effect of activity map iteration:

• The path is already pretty good without it
• Some parts, it seems to actually make worse!
• We have no evidence that it actually helps the cars driving, since the region manager tries to keep them so far apart anyways
• We didn’t have time to build any cool visualization tools :(

No iteration

2 iterations

Active collision avoidance using ORCA

• Every vehicle controls itself based on its surroundings
• 50/50 shared responsibility between vehicles
• Custom obstacle collision avoidance using raycast - creates appropriate constraints for each ray that detects obstacles
• New: Cars prefer slowing down rather than turning
• New: In equal situations, the car prefers turning right (eg: when two cars meet each other, both turn right for smoother avoidance)

Region Manager

• Controls the traffic through the entire map
• Works like traffic lights
• Each region has a certain capacity and no more vehicles are allowed to enter in case the capacity is exceeded
• New: Each vehicle looks at a certain number of future regions and only proceeds if all those regions are allowed to enter

Evaluation

• Visualization tools took time from development, but helped immensely with ensuring bug-free implementations of algorithms.
• Activity map didn’t quite work
• ORCA did not consider the car’s physics - worked better on the drone
• Active collision avoidance is probably more practical in the real world

Overall, our solution worked!

​

However, it is not fast. It seems like full temporal planning (like group 1 did) is the way to go for fast solutions.

​

Still, we are happy with how it turned out.

Status report