Real-time Search

In computer graphics, Real-time search refers to the set of search algorithms that serve for Navigation and Path-finding of an agent in a dynamic environment, where the decision making is constantly affected by unpredictable forces such as moving obstacles. Since the obstacles between the start point and the goal are doing stochastic motions continuously, a real time reaction to the changing environment and a real time update for the chosen path become necessities.

Especially, real time search provides solutions for complex agent representation problems which are encountered in several significant digital industries such as film production and game making, where enormous virtual human agents have to be simulated in the same complex scene with an authentic and collision-less motion simultaneously.

Broad categorize

Extensive literature exists on path planning for multiple agents in robot motion planning and virtual environments.^[1] 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 ^[2] and Elastic Road-maps.^[3]

Algorithms for Real-Time Search

Multi-Domain Real-time Planning^[4]

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^[5]

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^[6]

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 hi

gh dimensional spaces efficiently. Because, RRT avoids the state explosion that discretization faces. Moreover, they can keep complicated kinematic constraints .^[7] 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 a 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.^[8]

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.^[9]

Pseudo code of Anytime Dynamic A* search^[10]

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');

References

External links

• Real-time Navigation of Independent Agents Using Adaptive Roadmaps
• Path Optimization by Elastic Band