Real-time path planning in dynamic virtual environments using multiagent navigation graphs

We present a novel approach for efficient path planning and navigation of multiple virtual agents in complex dynamic scenes. We introduce a new data structure, Multi-agent Navigation Graph (MaNG), which is constructed using first- and second-order Voronoi diagrams. The MaNG is used to perform route planning and proximity computations for each agent in real time. Moreover, we use the path information and proximity relationships for local dynamics computation of each agent by extending a social force model [Helbing05]. We compute the MaNG using graphics hardware and present culling techniques to accelerate the computation. We also address undersampling issues and present techniques to improve the accuracy of our algorithm. Our algorithm is used for real-time multi-agent planning in pursuit-evasion, terrain exploration and crowd simulation scenarios consisting of hundreds of moving agents, each with a distinct goal.     

Offline gain optimization in kinodynamic motion planning based on a harmonic potential field

A method of automatically optimizing gains is described for kinodynamic motion planning related to a controlled system consisting of a point mass. Kinodynamic motion planning proposed by Masoud has some gains and it is difficult to optimize such gains manually due to its interaction. Note, however, that any method for optimizing the gains has not been mentioned yet. Therefore, a method for optimizing all gains included in the kinodynamic motion planning is proposed by using a genetic algorithm.     

Provably good approximation algorithms for optimal kinodynamic planning: Robots with decoupled dynamics bounds

We consider the following problem: given a robot system, find a minimal-time trajectory that goes from a start state to a goal state while avoiding obstacles by a speed-dependent safety margin and respecting dynamics bounds. In [1] we developed a provably good approximation algorithm for the minimum-time trajectory problem for a robot system with decoupled dynamics bounds (e.g., a point robot in ³). This algorithm differs from previous work in three ways. It is possible (1) to bound the goodness of the approximation by an error term; (2) to bound the computational complexity of our algorithm polynomially; and (3) to express the complexity as a polynomial function of the error term. Hence, given the geometric obstacles, dynamics bounds, and the error term, the algorithm returns a solution that is-close to optimal and requires only a polynomial (in (1/)) amount of time.We extend the results of [1] in two ways. First, we modify it to halve the exponent in the polynomial bounds from 6d to 3d, so that the new algorithm isO(c ^d N 1/)^3d ), whereN is the geometric complexity of the obstacles andc is a robot-dependent constant. Second, the new algorithm finds a trajectory that matches the optimal in time with an factor sacrificed in the obstacle-avoidance safety margin. Similar results hold for polyhedral Cartesian manipulators in polyhedral environments.The new results indicate that an implementation of the algorithm could be reasonable, and a preliminary implementation has been done for the planar case.This paper describes research done at the Computer Science Robotics Laboratory at Cornell University. Support for our robotics research there is provided in part by the National Science Foundation under Grant Nos. IRI-8802390 and IRI-9000532, by a Presidential Young Investigator award, and in part by the Mathematical Sciences Institute, Intel Corporation, and AT&T Bell Laboratories.     

Near field acoustic localization under unfavorable conditions using feedforward neural network for processing time difference of arrival

Using time difference of arrival (TDOA) is one of the two approaches that utilize time delay for acoustic source localization. Combining the obtained TDOAs together with geometrical relationships within acoustic components results in a system of hyperbolic equations. Solving these hyperbolic equations is not a trivial procedure especially in the case of a large number of microphones. The solution is additionally compounded by uncertainties of different backgrounds. The paper investigates the performance of neural networks in modelling a hyperbolic positioning problem using a feedforward neural network as a representative. For experimental purposes, more than 2000 sound files were recorded by 8 spatially disposed microphones, for as many arbitrarily chosen acoustic source positions. The samples were corrupted by high level correlated noise and reverberation. Using cross-correlation, with previous signal pre-processing, TDOAs were evaluated for every pair of microphones. On the basis of the obtained TDOAs and accurate sound source positions, the neural network was trained to perform sound source localization. The performance was examined using a large number of samples in terms of different acoustic sensors setups, network configurations and training parameters. The experiment provided useful guidelines for the practical implementation of feedforward neural networks in the near-field acoustic localization. The procedure does not require substantial knowledge of signal processing and that is why it is suitable for a broad range of users.     

Real-time path planning of autonomous robots in a two-dimensional unknown dynamic navigation environment

This paper deals with the real-time path planning of an autonomous mobile robot in two-dimensional, unknown, dynamic multiple robot navigation space. In particular, a collision-free navigation path planning strategy is presented in real time by using a heuristichuman like approach. The heuristic scheme used here is based on thetrial and error methodology with the attempt to minimize the cost of the navigation efforts, when time plays a significant role. Past built-up navigation experience and current extracted information from the surrounding environment are used for the detection of other moving objects (robots) in the same navigation environment. Moreover, the determination of asecure navigation path is supported by a set of generic traffic priority rules followed by the autonomous robots moving in the same environment. Simulated results for two moving objects in the same navigation space are also presented.     

Real-time management of berth allocation with stochastic arrival and handling times

In this research we study the berth allocation problem (BAP) in real time as disruptions occur. In practice, the actual arrival times and handling times of the vessels deviate from their expected or estimated values, which can disrupt the original berthing plan and possibly make it infeasible. We consider a given baseline berthing schedule, and solve the BAP on a rolling planning horizon with the objective to minimize the total realized cost of the updated berthing schedule, as the actual arrival and handling time data is revealed in real time. The uncertainty in the data is modeled by making appropriate assumptions about the probability distributions of the uncertain parameters based on past data. We present an optimization-based recovery algorithm based on set partitioning and a smart greedy algorithm to reassign vessels in the event of disruption. Our research problem derives from the real-world issues faced by the Saqr port, Ras Al Khaimah, UAE, where the berthing plans are regularly disrupted owing to a high degree of uncertainty in information. A simulation study is carried out to assess the solution performance and efficiency of the proposed algorithms, in which the baseline schedule is the solution of the deterministic BAP without accounting for any uncertainty. Results indicate that the proposed reactive approaches can significantly reduce the total realized cost of berthing the vessels as compared to the ongoing practice at the port.     

Simulation of queueing network with time varying arrival rates

Queueing models are important in the analysis of many aspects of system or human behaviour. In such widely divergent fields as administrative processes, health services, traffic control, production control, computer communication networks, time sharing, and architecture, queueing analysis is indisposable for better understanding and ultimately synthesis of the system.However straight mathematical analysis is difficult, as the difference equations describing a queueing network are non-linear and of infinite dimensional. Due to this difficulty, time varying cases are seldomly included in the study of analytic solutions of queueing systems. In existing literature, the mean arrival rates are assumed independent of time. This assumption is of dubious validity as the arrival rate in actual operations varies with a twenty four hours period. While one can assume further that at every instant in time, the equilibrium condition for constant arrival rate is reached for the current arrival rate, it has never been verified that such is the case.An alternative approach is to reduce the queueing problem to finite dimensional and to simulate it on computer as is proposed in the present paper. The basic assumptions are (1) time-varying random arrival rate with Poisson statistics and (2) exponentially distributed service time. An algorithm and flow diagram for doing this is given. With the simulation techniques developed in this paper, we can study the dynamics of varying arrival rate. Simulation of a simple network shows that as the arrival rate approaches capacity, the divergence between simulated results and previous analytical results for the equilibrium condition become increasingly large. A conclusion is therefore that except for systems with very light loading, analytical results based on constant arrival rate are not accurate. Simulation is necessary if one is to obtain a true picture of the system.     

Path planning strategy for autonomous mobile robot navigation using Petri-GA optimisation

In this paper, a novel knowledge based genetic algorithm (GA) for path planning of multiple robots for multiple targets seeking behaviour in presence of obstacles is proposed. GA technique has been incorporated in Petri-Net model to make an integrated navigational controller. The proposed algorithm is based upon an iterative non-linear search, which utilises matches between observed geometry of the environment and a priori map of position locations, to estimate a suitable heading angle, there by correcting the position and orientation of the robots to find targets. This knowledge based GA is capable of finding an optimal or near optimal robot path in complex environments. The Petri-GA model can handle inter robot collision avoidance more effectively than the stand alone GA. The resulting navigation algorithm has been implemented on real mobile robots and tested in various environments to validate the developed control scheme.     

Real-time crowd motion planning

Real-time crowd motion planning requires fast, realistic methods for path planning as well as obstacle avoidance. In a previous work (Morini et al. in Cyberworlds International Conference, pp. 144–151, 2007), we introduced a hybrid architecture to handle real-time motion planning of thousands of pedestrians. In this article, we present an extended version of our architecture, introducing two new features: an improved short-term collision avoidance algorithm, and simple efficient group behavior for crowds. Our approach allows the use of several motion planning algorithms of different precision for regions of varied interest. Pedestrian motion continuity is ensured when switching between such algorithms. To assess our architecture, several performance tests have been conducted, as well as a subjective test demonstrating the impact of using groups. Our results show that the architecture can plan motion in real time for several thousands of characters.

Group planning with time constraints

Embedding planning systems in real-world domains has led to the necessity of Distributed Continual Planning (DCP) systems where planning activities are distributed across multiple agents and plan generation may occur concurrently with plan execution. A key challenge in DCP systems is how to coordinate activities for a group of planning agents. This problem is compounded when these agents are situated in a real-world dynamic domain where the agents often encounter differing, incomplete, and possibly inconsistent views of their environment. To date, DCP systems have only focused on cases where agents’ behavior is designed to optimize a global plan. In contrast, this paper presents a temporal reasoning mechanism for self-interested planning agents. To do so, we model agents’ behavior based on the Belief-Desire-Intention (BDI) theoretical model of cooperation, while modeling dynamic joint plans with group time constraints through creating hierarchical abstraction plans integrated with temporal constraints network. The contribution of this paper is threefold: (i) the BDI model specifies a behavior for self interested agents working in a group, permitting an individual agent to schedule its activities in an autonomous fashion, while taking into consideration temporal constraints of its group members; (ii) abstract plans allow the group to plan a joint action without explicitly describing all possible states in advance, making it possible to reduce the number of states which need to be considered in a BDI-based approach; and (iii) a temporal constraints network enables each agent to reason by itself about the best time for scheduling activities, making it possible to reduce coordination messages among a group. The mechanism ensures temporal consistency of a cooperative plan, enables the interleaving of planning and execution at both individual and group levels. We report on how the mechanism was implemented within a commercial training and simulation application, and present empirical evidence of its effectiveness in real-life scenarios and in reducing communication to coordinate group members’ activities.     

Deadlock-free motion planning using the Laplace potential field

In this paper we introduce a motion planning method which uses an artificial potential field obtained by solving Laplace's differential equation. A potential field based on Laplace's equation has no minimal point; therefore, path planning is performed without falling into local minima. Furthermore, we propose an application of the motion planning method for recursive motion planning in an uncertain environment. We illustrate the robot motion generated by the proposed method with simulation examples.     

Real-time model based geometric reasoning for vision-guided navigation

This paper describes results of a real-time model based geometric reasoning module for autonomous vision-guided road following. Vision-guided road following requires extracting road boundaries from images in real time to guide the navigation of autonomous vehicles on a roadway. The detected road region boundary is error prone due to imperfect image segmentation. To achieve robust system performance, a geometric reasoning module that uses spatial and temporal constraints to perform model based reasoning is used. Local geometric supports for each road edge segment are collected and recorded and a global consistency checking is performed to obtain a consistent interpretation of the raw data. Cases involving incomplete sensor data, curved roads where only one side of the road is visible, and incorrect segmentation due to shadows, road patches, or unusual road conditions, can usually be detected and corrected. The image segmentation results are what the vision system sees. The geometric reasoning results are what the vision system perceives. This reasoning module has been integrated into a road following system which is capable of supporting autonomous robot road following at 24 km/hr.     

Retrial queuing system with Markovian arrival flow and phase-type service time distribution

We consider a multi-server queuing system with retrial customers to model a call center. The flow of customers is described by a Markovian arrival process (MAP). The servers are identical and independent of each other. A customer’s service time has a phase-type distribution (PH). If all servers are busy during the customer arrival epoch, the customer moves to the buffer with a probability that depends on the number of customers in the system, leaves the system forever, or goes into an orbit of infinite size. A customer in the orbit tries his (her) luck in an exponentially distributed arbitrary time. During a waiting period in the buffer, customers can be impatient and may leave the system forever or go into orbit. A special method for reducing the dimension of the system state space is used. The ergodicity condition is derived in an analytically tractable form. The stationary distribution of the system states and the main performance measures are calculated. The problem of optimal design is solved numerically. The numerical results show the importance of considering the MAP arrival process and PH service process in the performance evaluation and capacity planning of call centers.     

Wheeled mobile robot navigation using proportional navigation

We present a method for wheeled mobile robot navigation based on the proportional navigation law. This method integrates the robot's kinematics equations and geometric rules. According to the control strategy, the robot's angular velocity is proportional to the rate of turn of the angle of the line of sight that joins the robot and the goal. We derive a relative kinematics system which models the navigation problem of the robot in polar coordinates. The kinematics model captures the robot path as a function of the control law parameters. It turns out that different paths are obtained for different control parameters. Since the control parameters are real, the number of possible paths is infinite. Results concerning the navigation using our control law are rigorously proven. An extensive simulation confirms our theoretical results.     

Motion planning and control for mobile robot navigation using machine learning: a survey

Autonomous Robots - Moving in complex environments is an essential capability of intelligent mobile robots. Decades of research and engineering have been dedicated to developing sophisticated...     

Autonomous navigation and obstacle avoidance using navigation laws with time-varying deviation functions

In this paper we introduce a new family of navigation functions for robot navigation and obstacle avoidance. The method can be used for both path finding and real-time path planning. Each navigation function is composed of three parts: a proportionality term, a deviation function and a deviation constant. Deviation functions are time-varying functions satisfying certain conditions. These functions and parameters are updated in real-time to avoid collision with obstacles. Our strategy uses polar kinematics equations to model the navigation problem in terms of the range and direction between the robot and the goal. The obstacles are mapped to polar planes, and represented by the range and the direction from the robot or the final goal in polar coordinates. This representation gives a certain weight to the obstacles based on their relative position from the robot and facilitates the design of the navigation law. There exists an infinite number of navigation functions obtained by changing the proportionality constant, the deviation constant or the deviation function. This offers an infinite number of possibilities for the robot's path. Our navigation strategy is illustrated using an extensive simulation where different navigation parameters are used.     

Real-time collision-free motion planning of a mobile robot using a Neural Dynamics-based approach

A neural dynamics based approach is proposed for real-time motion planning with obstacle avoidance of a mobile robot in a nonstationary environment. The dynamics of each neuron in the topologically organized neural network is characterized by a shunting equation or an additive equation. The real-time collision-free robot motion is planned through the dynamic neural activity landscape of the neural network without any learning procedures and without any local collision-checking procedures at each step of the robot movement. Therefore the model algorithm is computationally simple. There are only local connections among neurons. The computational complexity linearly depends on the neural network size. The stability of the proposed neural network system is proved by qualitative analysis and a Lyapunov stability theory. The effectiveness and efficiency of the proposed approach are demonstrated through simulation studies.     

Space and time sensor fusion using an active camera for mobile robot navigation

We propose a sensor-fusion technique where the data sets for previous moments are properly transformed and fused into the current data sets to allow accurate measurements, such as the distance to an obstacle or the location of the service robot itself. In conventional fusion schemes, measurements are dependent on the current data sets. As a result, more sensors are required to measure a certain physical parameter or to improve the accuracy of a measurement. However, in this approach, instead of adding more sensors to the system, the temporal sequences of the data sets are stored and utilized to improve the measurements. The theoretical basis is illustrated by examples, and the effectiveness is proved through simulations. Finally, the new space and time sensor fusion (STSF) scheme is applied to the control of a mobile robot in an unstructured environment and a structured environment.This work was presented in part at the 8th International Symposium on Artificial Life and Robotics, Oita, Japan, January 24–26, 2003     

一种音频测距信号到达时刻估计方法

对音频测距信号到达时刻的精确估计是利用音频信号实现远距离无线传感器网络节点定位的关键。研究比较了几种常用的音频测距信号到达时刻估计方法,并提出了一种基于数字整流处理的到达时刻估计方法。它包括信噪比增强、去除直流分量、全波整流、低通滤波、到达时刻估计等过程。该方法在以dsPIC6014A单片机为控制器的节点进行了实验验证,测试结果表明:处理4 096点(12位量化)数据的计算时间约为1.5 s(10MHz时钟),30m距离处的时间值估计误差小于3.5%。