User:AsluisUCSB/sandbox/Real-Time Path Planning

Real-Time Path Planning is the usage of real-time computations and A.I. in order to avoid collisions. Real-time path planning algorithms have various applications such as video games, autonomous vehicles, simulations, and robotics. In other words, Real-Time Path Planning is the term used to describe the algorithm that is able to detect objects and avoid collisions, all while helping an entity reach a certain destination.

Real world applications

Virtual (Video Games)

Video game entities must sometimes move from one point to another without colliding with unnecessary game objects, and the computations needed are sometimes performed in real-time in order to let the entity adapt to any changes made in the virtual scene by a player. If a game has a non-human-controlled character moving from one place to another in an area that could be altered by a player (such as a field that lets players place objects in it), then that character is very likely to be using some sort of Real-Time Path Planning algorithm to achieve such a feat.

Problem with Real-Time Path Planning in Video Games

Whenever a group of autonomous entities all have the same destination, some individual member of the group sometimes strays away from the pack and takes a less effective route to the destination, as seen on the picture to the right. This problem is commonly noticed in games, such as Clash of Clans, that rely a lot on real-time path planning for their in-game characters.

Autonomous Vehicles

Software is important when it comes to autonomous vehicles due to their collision-avoiding nature which can only be achieved through the usage of software. In order for a vehicle to truly be autonomous, it must be able to avoid collisions and choose the safest path to reach a certain location because it would be transporting people or goods, so the safety of the passenger is incredibly important. Real-Time Path Planning algorithms allow autonomous vehicles to plan out a safe path to follow that avoids obstacles and generates a trajectory to ensure safety. The sensors on the side mirrors of many cars show in what state the trajectory-sensing technology currently is (excluding experimental technology).

Robotics

Computing a possible path for robots can become exponentially complex as the entity is given more freedom to move. Real-Time Path Planning for a bipedal humanoid robots is computed by comparing the relative distance between the robot and the nearest obstacle. Some bipedal robots assume that their environment has a noticeable difference between a flat horizontal floor and an obstacle in order to be able to accurately compute the distance between the robot and any potential obstacle.

A prime example that combines both robotics and autonomous vehicles would have to be the robot developed in a IEEE meeting which used Google Maps to navigate from one location to another, as it can be seen with the general outline of the algorithm they used.

General outline of the algorithm used by the IEEE in a meeting.

How it works

Pseudo-Code

Pseudo-Code is a way of outlining an algorithm in such a way that it could be implemented in any language. In other words, pseudo-code does not contain anything related to any specific language, thus making it a general outline that enables people to implement the algorithm in any programming language.

"Input: Agent pi , Goal position gi , Set of sites P, MaNG MG(P)

Output: Path Si from current position to goal position

k ← LocatePoint(gi)

if k = i then

Si ← edge(π(pi),gi)

return

Compute Vi ← set of black vertices in Vor(pi |P)

Compute Ei ← set of black edges in Vor(pi |P)

if Vi 6= 0/ and π(pi) ∈/ Vi then

Augment MG(P) with green edges

e j = (π(pi), v j)∀v j ∈ V

Assign weight to e j ,w(e j) ← d(π(pi), v j)

else

foreach edge e j ∈ Ei do

Compute v j ← closest point on e j to π(pi)

Augment MG(P) with green edge e j = (π(pi), v j)

Assign weight to e j ,w(e j) ← d(π(pi), v j)

end

Compute Vk ← set of red vertices in Vor(pk |P)

Augment MG(P) with green edges e j = (gi , v j)∀v j ∈ V

Assign weight to e j ,w(e j) ← d(gi , v j)

Add green labels to each edge e j ∈ Ei

Si ← ShortestPath (pi ,gi ,MG(P))

Remove green labels from each edge e j ∈ Ei

Remove all green edges from MG(P)"

Essentially what the above algorithm does is analyze the entity's environment and its objective in order to compute a path for the entity that uses it in order to help it reach its goal. In this particular implementation of a Real-Time Path Planning algorithm, a site is any "point, open edge, open triangle, or a connected polygonal object" in two dimensions, and an agent is the robot or virtual entity that is using the algorithm. Also, 'MaNG' in this particular case stands for "Multi-agent Navigation Graph" and is used to deal with multiple agents, or entities, in the same environment because each individual agent would be an obstacle for any other agent.