User:AsluisUCSB/sandbox/Real-Time Path Planning
This is not a Wikipedia article: It is an individual user's work-in-progress page, and may be incomplete and/or unreliable. For guidance on developing this draft, see Wikipedia:So you made a userspace draft. Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL |
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
[edit]Virtual (Video Games)
[edit]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.[1] 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
[edit]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
[edit]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. [2] The sensors on the side mirrors of many cars show in what state the trajectory-sensing technology currently is (excluding experimental technology).
Robotics
[edit]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. [3]
A prime example that combines both robotics and autonomous vehicles would have to be the robot developed in a IEEE meeting[4] 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.
How it works
[edit]Pseudo-Code
[edit]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)"[5]
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"[5] 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"[5] 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.
References
[edit]- ^ Overmars, Mark. "Path Planning for Games" (PDF). http://www.cs.uu.nl/education/.
{{cite web}}
: External link in
(help)|website=
- ^ Katrakazas, Christos; Quddus, Mohammed; Chen, Wen-Hua; Deka, Lipika (2015-11-01). "Real-time motion planning methods for autonomous on-road driving: State-of-the-art and future research directions". Transportation Research Part C: Emerging Technologies. 60: 416–442. doi:10.1016/j.trc.2015.09.011. ISSN 0968-090X.
- ^ Gutmann, Jens-Steffen. "Real-Time Path Planning for Humanoid Robot Navigation" (PDF). Intelligent Systems Research Laboratory – via International Joint Conferences on Artificial Intelligence.
- ^ "Real time implementation of path planning algorithm with obstacle avoidance for autonomous vehicle - IEEE Conference Publication". ieeexplore.ieee.org. Retrieved 2018-11-04.
- ^ a b c Sud, Avneesh. "Real-time Path Planning for Virtual Agents in Dynamic Environments" (PDF). Department of Computer Science, University of North Carolina at Chapel Hill. doi:10.1145/1410000/1401206/a55-sud (inactive 2022-06-08).
{{cite journal}}
: CS1 maint: DOI inactive as of June 2022 (link)