TTC Motion Handling

For this project, I created a Time-to-Collision (TTC) motion-planning simulation featuring A* path-finding and a PRM-based roadmap. This project was completed in C++. Here are a couple of video examples and then some information on features, benchmarks, difficulties, and a way to see my source code!

Few details for the videos below:

  • This is the first large C++ project that I have ever built from the ground up, besides the MinGFX library. It took me a while to realize C++’s default parameter passing is by value, and thus I was making hundreds of thousands of copies while constructing my adjacency lists.
  • In my A* implementation and path smoothing, my actors kept on taking funny routes while trying to avoid collisions. I had been implementing this with collision detection through vector projections, but I hadn’t been checking two things:
    • If the dot product of the path-to-obstacle and path-to-target-node were positive, aka the obstacle was in the direction of my target node. My algorithm was giving false results, telling the robots they were going to collide with an obstacle behind them.
    • If the length of the path between nodes was less than the length needed for a collision to happen. Originally, actors could not move in the general direction of an obstacle, regardless if they moved merely a fraction. So I implemented a check to see if the length of the vector between my start and target nodes was less then the distance necessary for a collision. This allowed actors to move in the direction of an obstacle until their movement would actually cause a collision.

1) Actors going to opposite ends without obstacles

2) Actors going to opposite ends with obstacles

3) Actors going to opposite ends with local minimum at top

4) Actors all going towards common goal with obstacles

5) Two actors trying to reach the others starting position

  • This is a case where the TTC algorithm has some issues. The actors collision force tries to push them in the opposite direction of a collision, backwards. But their goal force tries to push them in the direction of their goal, forwards. The two actors end up in some form of limbo.
  • Ideally, in this situation, the two robots would re-run their A* algorithm and find new paths to the goal. Since the actor’s positions are not in the PRM, we could find the closest node to each actor and use it as their position in finding a new path

Features:

  • Using MinGFX graphics library by Dan Keefe (https://github.com/ivlab/MinGfx)
  • Real-time rendering
  • PRM/A* path finding
  • Path smoothing
  • Modern OpenGL indexed lists

Benchmarks:

  • 500 Node PRM (Probabilistic Roadmap)
  • 60 FPS

Roadblocks during creation:

  • This is the first large C++ project that I have ever built from the ground up, besides the MinGFX library. It took me a while to realize C++’s default parameter passing is by value, and thus I was making hundreds of thousands of copies while constructing my adjacency lists.
  • In my A* implementation and path smoothing, my actors kept on taking funny routes while trying to avoid collisions. I had been implementing this with collision detection through vector projections, but I hadn’t been checking two things:
    • If the dot product of the path-to-obstacle and path-to-target-node were positive, aka the obstacle was in the direction of my target node. My algorithm was giving false results, telling the robots they were going to collide with an obstacle behind them.
    • If the length of the path between nodes was less than the length needed for a collision to happen. Originally, actors could not move in the general direction of an obstacle, regardless if they moved merely a fraction. So I implemented a check to see if the length of the vector between my start and target nodes was less then the distance necessary for a collision. This allowed actors to move in the direction of an obstacle until their movement would actually cause a collision.

Source Code:

Share: