Elements Attempted:

• Single Agent Navigation: Simulated a 3D agent (human figure) moving through a cluttered 3D environment (trees and a barn). As the human figure moves through the environment, its bounding geometry does not overlap with any of the obstacles. There is no unnatural hesitation or large changes in speed.

• 3D Rendering & Camera: The environment is a high-quality 3D rendering of trees and barn objects. There is lighting direction set up as well. A 3D camera was incorporated in the implementation for viewing.

• Improved Agent & Scene Rendering: The agents in all my simulations in this project are rendered with 3D models. All the objects in the scene are also rendered with realistic 3D models (objects).

• Orientation Smoothing: The human figures I used in all my simulations have an orientation based on their direction of motion (facing the way they are traveling). The turning motion is quite smooth.

• User Scenario Editing:

  • • In both single agent and multi agent navigation simulations, user can move the silo obstacle to change the scenario. User can create new random obstacle courses by pressing 'r'

    • In crowd simulation, user can select 3 different types of scenarios pressing key '1', '2', or '3'. User can also create new random agents placement within scenario type 1 and 2 by pressing 'r'. (scenario 3 is a fixed position scene, there is no location randomness)

• Real-time User Interaction: All my simulations have multiple ways to interact and control the program as the program is running.

  • • Single/Multiple agents navigation:

      • • User can set start and goal position by mouse click (left goal, right start)

        • User can replay a scene by pressing 'o'

        • User can show planned path by pressing 'p' (second press will turn the path showing off).

        • User can get a different obstacle course by pressing 'r'

        • User can pause the agent(s) by pressing space key (second press will have the agent(s) moving again).

        • User can move the silo obstacle by pressing 'j', 'k', 'l', 'i'

• Crowd simulation:

  • • User can select 3 different types of scene by pressing '1', '2', '3'

    • User can replay a scene by pressing 'o' to set all agents to their start position in the last scene

    • User can create different random start and goal positions for the agents for scene types 1 and 2 by pressing 'r'

    • User can pause the agent(s) by pressing space key (second press will have the agent(s) moving again).

• Multi-agent Planning: Multiple agents (4 humans) moves simultaneously in the scene. All human objects move towards their own independent goals, each with their own planned path (sharing one underlying graph).

• Crowd Simulation: Multiple agents (20 human figures) moving simultaneously to their goals in a shared environment (a room), avoiding collisions with each other. I implemented TTC force and Prof.Guy's VO method. The result is quite good. The agents display smooth,anticipatory,collision-free motion. However, just as the professor had pointed out, VO still has some rotation jittery effect when two agents pass each other closely. This jittery effect is only visible when the agents are oriented to their direction of traveling. If rendering with symmetric geometry without orientation alignment, this jitter is not visible.

  • • I implemented 3 types of scenes for the crowd simulation:

      • 1. Random start positions and goal positions within the whole space for all agents

        2. All agents start in half of the room (locations are random), and their goals are in the other half of the room (locations are random)

        3. All agents are lined up on two perpendicular sides of the room and move to the other two sides. This results in many agents moves in a head on direction in a crowded space (multiple agents are moving in different contradictory directions right next to each other). In this scene, the VO's jittery effect is the most visible

Team Member

• Hailin Archer deak0007@umn.edu

Codes

https://github.com/CyberHolmes/CSCI5611/tree/master/Project3

User Interaction Controls

Start & Goal Position Selection With Mouse Click (Single Agent Navigation):

• left mouse click : goal position set to where the mouse is

  1. • right mouse click : start position set to where the mouse is

Obstacle Silo Control (Single Agent Navigation, Multiple Agent Navigation):

• j : x axis negative move (left)

• l : x axis positive move (right)

• i : y axis negative move (up)

• k : y axis negative move (down)

Replay (Single Agent Navigation, Multiple Agent Navigation, crowds) (All Simulations):

• o: return agent(s) to their start position without modifying the scene

Show Planned Path(s) (Single Agent Navigation, Multiple Agent Navigation):

• 1. • p: show planned path by pressing 'p' (second press will turn the path showing off)

Pause Agent(s) Movement (Single Agent Navigation, Multiple Agent Navigation, crowds) (All Simulations):

• 1. • space key: pause the agent(s) by pressing space key (second press will have the agent(s) moving again)

Restart With A Different Objects Location (Single Agent Navigation, Multiple Agent Navigation, crowds) (All Simulations):

• r key: press once

Change Types Of Scene In Crowd Simulation:

• key '1': agents are randomly placed in the whole room, agents' goals are also randomly placed in the whole room

• key '2': agents are randomly placed in half of the room, agents' goals are also randomly placed in the other half of the room

• key '3': agents are lined up against two perpendicular sides of the wall and their goal are the opposite sides of the room

3D Camera Control (All 3D simulations):

• 'w': positiveMovement.z

• 's': negativeMovement.z

• 'a': negativeMovement.x

• 'd': positiveMovement.x

• 'q': positiveMovement.y

• 'e': negativeMovement.y

• LEFT: negativeTurn.x

• RIGHT: positiveTurn.x

• UP: positiveTurn.y

• DOWN: negativeTurn.y

Single Agent Navigation

Description

An agent (rendered with a 3D human figure object) moves from one corner of the field to the diagonal corner of the field. There are randomly placed brushes in the field. There is also a silo (movable by the user) in the field. The agent moves around those obstacles in a relatively short path to her target.

I implemented A* search algorithm, which gives an optimal path. I also implemented skip ahead method, where if there is a direct path to the goal or the next destination on the path, the agent will take the direct path, instead of strictly following the planned path.

User can replay a scene, pause the agent, start a new obstacle course, move the silo and show the planned path.

Code

https://github.com/CyberHolmes/CSCI5611/tree/master/Project3/SingleAgentNavigation_3D

Video

Multiple Agents Navigation

Description

4 agents (rendered with four different 3D human figure objects) moves from four different corners of the field to the diagonal corners of the field. There are randomly placed brushes in the field. There is also a silo (movable by the user) in the field. The agent moves around those obstacles in a relatively short path to her target.

I implemented A* search algorithm, which gives an optimal path. I also implemented skip ahead method, where if there is a direct path to the goal or the next destination on the path, the agent will take the direct path, instead of strictly following the planned path.

I implemented TTC and VO algorithm based on the class activity codes for agent collision avoidance.

User can replay a scene, pause the agent, start a new obstacle course, move the silo and show the planned path.

Code

https://github.com/CyberHolmes/CSCI5611/tree/master/Project3/MultiAgentNavigation_3D_v0

Video

Crowd Simulation

Description

20 agents (rendered with four different 3D human figure objects) moves freely in a room. I implemented 3 types of scenes:

1. Agents are randomly placed in the whole room with their goals also randomly placed.

2. Agents are randomly placed in half of the room and their goals randomly placed in the other half of the room.

3. Agents are placed against two perpendicular walls and their goals are lined up on the other side of the room.

I implemented TTC and VO algorithm based on the class activity codes for agent collision avoidance.

User can replay a scene, pause the agents, restart a new scene within the same type with new placements, and switch between 3 different types of scenes.

I also implemented a more efficient way of finding non-overlapping random placements.

Code

https://github.com/CyberHolmes/CSCI5611/tree/master/Project3/CrowdSimulation

Video

Tools/Libraries Used

• The codes from CSCI5611 class live activities session

• The 3D Camera class provided in class

• 3D objects shared by Prof. Guy

Other Resources Used

• processing.org: processing programming reference, general language tutorial

Difficulties Encountered:

• Due to another class's final exam and final project (presentation and paper), I only had two days to work on this project. With young children at home, I didn't have enough time.

• Figuring out how to load and orient the 3D objects took me some time.

• I attempted to minimized the occasional rotation 'jitter' in the crowd simulation, but ran out of time.

Art Contest