Behavior Trees

Animated story :
This is a story between two legends - Mr.Samurai Sama and Mr.Dead Shot. One day Samurai sama meets with Dead Shot and they talk about a lot of stuff for sometime. In the conversation, Dead shot did a mistake of insulting Samurai sama. Samurai sama shouts and Dead shot and they both leave that place angry.
Dead shot consumed by anger, plans to kill Samurai sama with his gun. Samurai sama notices Dead shot walking towords him with a gun. He senses that something is wrong and quickly hides behind a wall and draws his katana. When Dead shots walks in, Samurai sama slowly sneaks up behind him and swiftly slashes Dead shot. The End. Implementation affordance like sitting, drawing katana, holding on to something, attacking. Here is the YouTube link of our game.

The online deployment of the game can be found here. and the git repository here.

Pathfinding using A-star

In this assignment, we implement A-star algorithm for finding the path in a grid environment.

A brief discussion about the A-star algorithm (From wikipedia)

A* uses a best-first search and finds a least-cost path from a given initial node to one goal node (out of one or more possible goals). As A* traverses the graph, it builds up a tree of partial paths. The leaves of this tree (called the open set or fringe) are stored in a priority queue that orders the leaf nodes by a cost function, which combines a heuristic estimate of the cost to reach a goal and the distance traveled from the initial node. Specifically, the cost function is

.

Here, g(n) is the known cost of getting from the initial node to n; this value is tracked by the algorithm. h(n) is a heuristic estimate of the cost to get from n to any goal node. For the algorithm to find the actual shortest path, the heuristic function must be admissible, meaning that it never overestimates the actual cost to get to the nearest goal node. The heuristic function is problem-specific and must be provided by the user of the algorithm.

We first used two heuristics, namely  Manhattan distance and Euclidean distance as they both are admissible and consistent heuristic.  Then we proceeded to compare the results of weighted heuristics. Following are some video clips demonstrating our results.

Using Eucliedian as heuristic

                                      

                                                       Using Manhattan as heuristic

Next, we checked how different ways of resolving the ties(with same lowest f-value) would imapct the solution

                                      

Tie breaking in favour of smaller 'g'

Tie breaking in favour of larger 'g'

In the final part we dicuss how altering the weight of the heuristic function affects the optimality and speed of the search.  Please refer the follwing table which compares the pathlength/#nodesexpanded against various weights of the heuristic. 

We observe that with the increase in the weight of heuristic function, the number of nodes expanded decreases as evident from the table shown above. However, the path returned is not optimal as the path increases with the increase in weights. This is due the fact the heuristic is now no longer admissible. 

Social Forces Implementation

As a part of course assignment, the Social Forces model has been implemented for obstacle avoidance. The model is then tested in various bottleneck test cases.

The Algorithm :

The Social Forces model computes various forces exerted on a agent by the environment. It then adds the exerted force with the force  required by the agent to reach the goal(F_pref) .

F = F_goal + F_agents + F_walls

F_agents & F_walls includes the proximity force, repulsion force(in case of collision) and sliding friction force(in case of collision) by obstacles/other agents.

Code : https://github.com/CG-F15-10-Rutgers/SteerLite (Forked from SteerLite parent repo)

The model is run against several test cases and the results are recorded. Following are the video links :

(a) Hallway one-way

(b) Hallway two-way

(c) Hallway four-way

(d) Bottleneck evacuation

Futher improvements : The efficiency can be further improved by tweaking the constant parameters of the Social Forces algorithm as per  the use-case.