HW3 - Motion Planning

Jackson Kruger and Kieran Lieberg

The source code for this project can be found on Github. A zip of the compiled executable for Windows and supporting files can be downloaded HERE. This simulation was written with C++ OpenGL for Windows.

CSCI5611MotionPlanning.zip

MotionPlanning.exe

Features

Checkin - http://www-users.cselabs.umn.edu/~kruge203/CSCI5611/HW3/MotionPlanning.html (10)
Flocking simulation (70)
- These features are clearly shown in the "Flocking Simulation" section below
'Nicely rendered' 3d scenes with models to give context (10)
Support full 3D navigation (10)
Allow user to control man placing seeds for birds, setting goals at runtime (<15)
3D rendering of scenario and characters (5)
Animate the agent as a walking virtual character (< 15)
A* for graph search (~5)
- The graph search we first implemented was Greedy breadth-first search. Unsurprisingly, Greedy BFS was generally faster than A*, as greedy BFS did not produce optimal solutions. With Greedy BFS, finding a solution out of 500 nodes on a certain scenario took 1-1.3ms, while A* took about 4-4.5ms on the same scenario.
Use a KD-tree to accelerate nearest neighbor search during PRM construction (10)
- Performance results are shown and discussed in the section "KDTree vs Brute Force PRM Construction" below
Path smoothing (5)
Game-like scenario (5)

Flocking Simulation

The agents in the following videos use boids as their local interaction technique. Each boid is affected by a separation force, a cohesion force, an alignment force, a local obstacle avoidance force, and a global navigation path-following force. The path following force applies a force to reach a desired travel speed goinging directly toward the furthest visible node on the planned path. All global path planning is done using A* over a single PRM that is constructed using a KDTree at the beginning of the simulation. Each agent effectively temporarily adds its own start and goal to the PRM when it has a path to plan, then removes them after the planning is finished. If an agent is pushed such that it can no longer see any part of its path, it re-runs A* from its current position to the goal.

Group Interactions Scenario #1 - Group Goals

The following demo shows these general behaviors. In the demo, there are four groups of five boids each. When any member of the group reaches its goal, a new goal is chosen for the entire group (with each boid's goal getting a small random perturbation). Each boid runs A* to find the optimal path to the goal, sometimes leading to (or helping recover from) a bird getting separated from its group. The boid forces pay no heed to which groups boids are in. At 0:06, debug mode is turned on. The PRM is shown by the grey spheres and the blue lines connecting them. Each boid's end goal is shown in orange, while the furthest visible node toward that goal along the path is shown in green.

General Group Interactions.mp4

Group Interactions Scenario #2 - Independent Goals

This demo shows 20 boids each navigating to their own goals continuously. This is using a different set of tuning parameters from the demo above. You can see that even though the boids always have different goals, they sometimes fly together with other boids on the way to their goals.

Independent Goal Groups.mp4

Group Navigation Scenario #1 - Maze Navigation

The following demo shows a single boid group successully navigating through a maze of obstacles, avoiding local minima along the way. It also demonstrates that the obstacles are inflated in the configuration space by the (approximate) radius of the agents. If this were not the case, PRM nodes would be connecting through the visibly skinny maze walls (and would be placed nearer to them). This is especially apparent at the overhead shot shown a few seconds into the video.

Fully Successful Maze.mp4

Group Navigation Scenario #2 - 'Cup' Navigation

The following demo shows another boid group successully navigating out and around a 3D shape like a cup turned on its side. The agents start inside the cup and must reach a goal (initially) on the other side of the cup. The boids successully navigate out and around the cup to reach their goal. Debug mode is turned on at 0:13 in this video, as the agents continually choose new random goals for the group.

GroupAvoidingLocalMinimaInCup.mp4

Failure

Because the simulation is based on a PRM, it is subject to the main weakness of PRM's: navigating through tight spaces. The image below shows a scenario where there is a space large enough for boids to fit through (accounting for configuration space inflation), yet the PRM does not connect across the gap, leaving two unconnected pieces of the PRM. This is because the points are sampled entirely randomly in the space outside the configuration space obstacles. The boids don't handle this well, as we assume in the code that the PRM graph is connected well enough to reach any valid goal within the configuration space.

Walk cycle

The Walk cycle was done last minute, as a way to make up for the time spent attempting to load an animation from a collada file. It was made very hastily in blender, exported as 12 .obj files, and are being cycled one every frame.

More Bird Player interaction

In our "Game" (see bottom) the birds eat the seeds (scooby snacks) the player places down. These seeds are implemented as goals for the boids. Once a boid reaches a seed, it stops (So it can eat the seed), and the seed is removed. The Boid will then rest until the player approaches it.

The player in the simulation is not an agent, instead there is an additional force applied to each boid, which is dependent on how far away the boid is from the player.

Misc

Tools/Libraries Used

This simulation is using OpenGL with C++. All code was written for Windows in Visual Studio. SDL is used to interface with Windows. The library SDL_Image is used to load textures. Glad is used as an interface to OpenGL. Collada Parsing (unfortunately only for geometry data ) was done using libxml.

Difficulties - Jackson

I struggled a bit writing the KDTree for using in PRM construction. I basically just followed the algorithm outlined on the Wikipedia page for KDTrees, but still ran into a few rather subtle bugs. I also chose to write the KDTree generically, so it could work in any dimension and with different types of nodes, which caused various troubles, and definitely wasn't worth it, as we've only ever used the KDTree for 3 dimenions. Boid parameter tuning was annoying, but not strictly difficult. A bug persisted in the agent's pathfinding for the majority of the project, resulting in agents occasionally being unable to find a path even though they should have been. I finally figured out at (as my last code change) that I wasn't cleaning up some of A*'s associated state in the nodes correctly, so it thought certain nodes had already been explored.

Difficulties - Kieran

I had a lot of difficulty attempting to load animation files. In fact, I spent a long time writing an Animation framework that had keyframes, animations, and would update VBO's, etc... That worked fine, however I completely underestimated the difficulty of writing even the most primitive skeletal animation collada parser. It took about 4 hours for me to read in the skinning data, so I gave up on the dream of having Motion-Capture data, and more than just a silly walk cycle in the project. I had numerous problems with the "game" aspect of the project, such as getting the height of the terrain. I still never figured out entirely how to solve the problem, and it is currently the most ugly artifact in the final version of the game. Also, when working with boids, I became quite frustrated with how much a tiny change in a parameter would cause the entire simulation to blow up.

KDTree vs Brute Force PRM Construction

Shown below is a table comparing the PRM construction times using a KDTree vs simple brute force. These times were measured in the same environment. Both methods connected the node to the N nearest nodes that were visible. The brute force method simply iterates over all nodes, maintaining a priority queue of N visible nodes sorted by their distance. In the table, the KDTree times have another time following in parentheses - this other time, KDTree construction time, is a subset of the total PRM construction time.

Untitled spreadsheet

Funny Bugs & Mistakes & Things

I tried to get agents to rotate to the direction they were moving at one point... it didn't work very well.

Agent Rotation Jumps.mp4

Things start going wrong at 0:17...

Fallback bad.mp4

The Game Scenario!

Come on Guys! We've got another Mystery to Solve!

Uh, guys?

...

Join Shaggy in his one-off adventure through a lonely forest, where he must defend his boredom by playing with the flock of birds that has mysteriously taken an interest to him, and his large amount of scooby snacks. I wonder if you should go find the rest of the gang? Probably not. Daphne should have considered the consequences of sleeping with Fred.

Press "F" to throw down some Scooby snacks. Then walk away, and wait for the birds to find them. The will stop (Because they are eating). While they are stopped, you can run up to them, and chase them away.

Commentary from a customer

i telported through the ground alot and most of the walkcyle didn't load but the birds ate most of the snacks before I destroyed the F button to the point that there was too much Scooby Snack to be eaten.

Report abuse