Real time Search

Broad categorize

Extensive literature exists on path planning for multiple agents in robot motion planning and virtual environments. At a broad level, these methods can be classified into global (or centralized) and local (or distributed) methods.

Global methods

The global paths represent the connectivity of collision-free space in terms of a graph or a roadmap, and require search algorithms to compute a path for each agent. Most roadmap based algorithms have been designed for motion planning for a single robot in a static environment and are generated based on random sampling techniques. Recently, some algorithms have been proposed to extend the roadmap-based methods to dynamic environments, multiple agents and deformable models. However, they have only been applied to relatively simple environments composed of a few robots and restricted obstacles. These approaches may not scale well to environments with a large number of independent agents.

Local methods

As compared to global methods, local methods are mostly reactive style planners based on variants of potential fields. They can handle large dynamic environments, but suffer from ‘local-minima’ problems and may not be able to find a collision-free path, when one exists. Often these methods do not give any kind of guarantees on their behaviour. Other route planning algorithms are based on path or roadmap modification, which allow a specified path for an agent to move or deform based upon obstacle motion. These methods include Elastic Bands and Elastic Road-maps.

Multi-Domain Real-time Planning

It is a real-time planning framework for multi-character navigation. It uses multiple heterogeneous problem domains of differing complexities for navigation in complex and dynamic virtual environments. It defines a set of problem domains (spaces of decision-making) which differ in the complexity of their state representations and the fidelity of agent control. These range from a static navigation mesh domain which only accounts for static objects in the environment, to a space-time domain that factors in dynamic obstacles and other agents at much finer resolution. These domains provide different trade-offs in performance and fidelity of control, requiring a framework that efficiently works in multiple domains by using plans in one domain to focus and accelerate searches in more complex domains.

Elastic Bands

It is a method that connects Path Planning and Collision Control System together.

While one conventional application for robot to interact with the environment in real time is to track the trajectory, on the other hand, the local behaviour which including a real-time collision avoidance function increases the level of competence of a control system. However, such local or reactive behaviours operate in real time can not solve the global problem of moving to an arbitrary goal.

The conventional solution is first to convert the path to a trajectory by time parametrization, then to track the trajectory. Path planners are often designed to find any feasible path, with little attention to its suitability for execution. Even if the time optimal parametrization is used, the path may have abrupt changes in direction or maintain little clearance from obstacles, requiring the robot to move slowly. In addition, if the controller is to implement some sort of real-time obstacle avoidance scheme then it must be able to deviate from the path. Once the robot is off the path, however, the controller has no global Information on how to reach the goal.

Predictive approaches

Such method approximates the trajectories of neighbouring agents in choosing collision-free velocities to do any-time path planning and

replanning in dynamic environments.

Crowd approaches paper

Crowd approaches compromise on control fidelity in an effort to efficiently simulate a large number of agents in real-time.

RRT Algorithm

Rapidly-exploring random trees algorithm employ randomization to explore large state spaces efficiently, and can form the basis for a probabilistically complete though non-optimal kinodynamic path planner.The strengths of RRT algorithm is that they can find plans in high dimensional spaces efficiently. Because, RRT avoids the state explosion that discretization faces. Moreover, they can keep complicated kinematic constraints.

RRTs have properties that make ideal them candidates for specific pathfinding instances. Firstly, an RRT will tend towards unexplored paths within a state space, maximizing the opportunity of finding the path of least resistance. An RRT's vertices are selected in such a way that their distribution approaches the sampling distribution. This means that the distributional behavior becomes evidently consistent as more vertices are explored. Lastly, RRTs simplicity, connectivity, and flexibility can serve as useful tools in constructing and amending path planning algorithms.

A planning algorithm using RRTs is as follows: Start with a trivial tree which consist only of the initial configuration. Then the iteration is: With probability p, find the nearest point in the current tree and extend it toward the goal g. Extending means adding a new point to the tree that extends from a point in the tree toward g while maintaining whatever kinematic constraints exist. In the other branch, with probability 1 − p, pick a point x uniformly from the configuration space, find the nearest point in the current tree, and extend it toward x. Thus the tree is built up with a combination of random exploration and biased motion towards the goal configuration.

Anytime Dynamic A* search

Anytime Dynamic A* search is an advanced algorithm derive from the basic A* search. It combines the strength of both re-planning algorithm and anytime algorithm. Thus, Anytime Dynamic A* search is able to perform without a fixed suboptimality bound and static environment.

Anytime Dynamic A* search quickly generates an initial suboptimal plan, bounded by an initial inflation factor which focuses search efforts towards the goal. This initial plan is iteratively improved by reducing the inflation factor until it becomes 1.0, thus guaranteeing optimality in the final solution.

The Anytime Dynamic A* search algorithm is formulated by combing the D* Lite (A more efficient, heuristic restricted version of D*), which copes with dynamic environments and ARA*, which deals with complex pathfinding. The similarities in algorithms can be merged to produce a single anytime, incremental replanning algorithm generates a solution set with improved bounds while working within a dynamic environment.

Pseudo code of Anytime Dynamic A* search

Procedure keys(s) if v(s) >= g(s)) return [g(s) + є * h(s); g(s)]; else return [v(s) + hs(s);v(s)];
procedure UpdateSetMembership(s) if( v(s) != g(s)) if(s not in CLOSED) insert/update s in OPEN with key(s); else if(s not in INCONS) insert s into INCONS;
else if(s in OPEN) remove s from OPEN; else if(s in INCONS) remove s from INCONS;
procedure ComputePath() while(key(s_goal)>min(key(s) s in OPEN) || v(s_goal) < g(s_goal)) remove s with the smallest key(s) from OPEN; if(v(s) > g(s)) v(s) = g(s); CLOSED = CLOSED + {s}; for each successor s' of s if(s' was not visited before) v(s') = g(s') = infinte; bp(s') = null; if(g(s')>g(s))+C(s,s') bp(s') = s; g(s')=g(bp(s')) + c(bp(s'),s'); UpdateSetMembership(s'); else //propagating underconsistency v(s) = infinite; UpdateSetMembership(s); for each successor s' of s if(s' was not visited before) v(s') = g(s') = infinite; bp(s') = null; if(bp(s') == s) bp(s') = argmin{ v(s'') + c(s'',s')} //s'' in Pred(s') g(s') = v(bp(s')) + c(bp(s'),s'); UpdateSetMembership(s');