Motion Planing

This project is finished by Haoran Yun and Zichen Yang.

Haoran Yun — Motion planing algorithm & Agents interaction algorithm & User control

Zichen Yang — 3D rendering & Film the demo video

Code

https://github.com/HaoranYun/animation_as3/tree/master/MotionPlanningCrowd

Video

Features shown in the video

00:05:

  • Implemented PRM as navigation and Boids as interaction.
  • Scenes are rendered in 3D.
  • Support full 3D navigation: using WSADQE and FHGTRY to move and rotate the camera.
  • Roadmap needs to account for the extent of the agents, and should support multiple obstacles in the environment: Paths are draw as black line in the scenario, multiple agents are using the asme roadmap to move to their goals.
  • Implement path smoothing(e.g., walk to the furthest visible node on path): when agents have go cross 60% of current segment, recursively check whether the following nodes are visible. When it meets the invisible one or the goal, stop the smooth function.

00:05 / 01:16:

  • 2 scenarios showing interesting interactions between the agents
  • 2 scenarios of groups of agents successfully navigating through environments with local minima.

00:10:

  • Allow users to add and move obstacle: By clicking on the floor, users are allowed to add obstacles in running time. At the same time, using arrow buttons could move the adding obstacles.
  • Allow the user to dynamic choose agent starts and goals at run time: After pressing TAB button, user could use arrow button to change the goal position in running time.
  • Allow user to control obstacles in real time, simulated agents should replan or react dynamically to the user: When user are moving the obstacle, paths would be re-plane according to the new position of obstacle.

02:47:

  • Implement and compare two different global navigation techniques: PRM and RRT are implemented. They are represented as one single agent in this situation. Run 100 times PRM/RRT and calculate the average time. For PRM, running time is : 0.02ms, for RRT, running time is : 0.15ms.
  • Implement an RRT: When the goal is still, PRM has better time performance than RRT. However, PRM possibly does not find a path and stuck at the start point since the milestones are randomly selected. RRT would always have a path toward the goal.
    • When the goal is moving, the agent with RRT could easily find the goal. It could reach the goal earlier than the agent with PRM .
    • The implementation of RRT is a little bit easier than PRM. In RRT, there is no global road map, so we don’t need to write an additional graph search function. But it is a little hard to find a proper period for periodically checking whether goal is reachable for existing nodes. It’s also hard to find a position along the line segment from the nearest neighbor in tree to the random nodes that not in obstacle space. We write a helper function, walkUntilNoCollision, to find the points.

03:15:

  • Implement and compare two different group interaction techniques: Boids and TTC are implemented and compared. Firstly Boids are used, the running time for Boids is 20117.0 frame, which is approximately 5.58s. Secondly, TTC is used, the running time is 56523.0 frame, which is approximately 15.7ms.

05:22:

  • A scenario where overall simulation breaks and produces odd behavior: In this scenario both groups of agents could not find the way to their goals. This is due to the drawback of PRM.

06:31:

  • Implemented A* and compare it with BFS: Time of different mode would be print out.

Difficulties

  • Parameter tuning in the boids algorithm is complicated. When implementing this algorithm, we found the agents always collide with each other since the separation force was much smaller other two forces. After enlarging the magnitude of separation force, the agents could keep a safe distance with others.
  • The points go beyond the floor area in RRT algorithm bring us some trouble. We write a helper function, walkUntilNoCollision, aims to find a position along the line segment from the nearest neighbor in tree to the random nodes that not in obstacle space. At first, we did not notice that the function generates points along the ray but not the line segment, and the points may locate beyond the floor area. After set up the boundary value, the problem was solved.
  • It is hard to organize the code when there are so many comparison need to be done. We set up three different mode for comparison.