Narrow Results

Exploration algorithms based on the Boustrophedon path seldom consider the impacts of a robot turning at corners on the exploration time. This paper proposes the Forecast-Island and Bidding A*-Euclidean Selecting Boustrophedon Coordination (FIBA*ESBC) algorithm to calculate the turning time at corners in the overall exploration time and introduces a method to estimate the walking time in the Boustrophedon paths in order to determine the directions for path execution. Typically, in bidding-based exploration tasks, the cost is the Euclidean distance between the current position of the robot and the target point. When there is an obstacle between two points, the cost is set to infinity. Therefore, the selected target point is sometimes not optimal. The FIBA*ESBC algorithm is based on the exploration cost of a combination of the Euclidean distance and A* algorithm walking path, which can effectively solve this problem. Because the bidding is based on a greedy algorithm, the robot has a small unexplored island in the later exploration stage; therefore, full exploration is not possible or requires a long time with several repeated paths. The FIBA*ESBC algorithm prioritizes the exploration and estimation of hidden and existing unexplored islands. It can realize complete exploration and decrease the exploration time. Through simulation experiments conducted using Gazebo and RViz, the feasibility of the FIBA*ESBC algorithm is verified. Moreover, a simulation experiment is conducted in MATLAB for comparison with other algorithms. The analysis of the experimental data shows that the proposed algorithm has a relatively short exploration time.

Significant advances have occurred in heuristic search for planning in the last eleven years. Many of these planners use A*-style search. We report on five sound and complete domain-independent forward state-space STRIPS planners in this paper. The planners are AWA* (Adjusted Weighted A*), MAWA* (Modified AWA*), AWA*-AC (AWA* with action conflict-based adjustment), AWA*-PD (AWA* with deleted preconditions-based adjustment), and AWA*-AC-LE (AWA*-AC with lazy evaluation). AWA* is the first planner to use node-dependent weighting in A*. MAWA*, AWA*-AC, AWA*-PD, and AWA*-AC-LE use conditional two-phase heuristic evaluation. MAWA* applies node-dependent weighting to a subset of the nodes in the fringe, after the two-phase evaluation. One novel idea in AWA*-AC-LE is lazy heuristic evaluation which does not construct relaxed plans to compute heuristic values for all nodes. We report on an empirical comparison of AWA*, MAWA*, AWA*-AC, AWA*-PD, and AWA*-AC-LE with classical planners AltAlt, FF, HSP-2 and STAN 4. Our variants of A* outperform these planners on several problems. The empirical evaluation shows that heuristic search planning is significantly benefitted by node-dependent weighting, conditional two-phase heuristic evaluation and lazy evaluation. We report on the insights about inferior performance of our planners in some domains using the notion of waiting time. We discuss many other variants of A*, state-space planners and directions for future work.

We argue that A*, the popular technique for path-finding for NPCs in games, suffers from three limitations that are pertinent to game worlds: (a) the grid maps often restrict the optimality of the paths, (b) A* paths exhibit wall-hugging behavior, and (c) optimal paths are more predictable. We present a new algorithm, VRA*, that varies map-resolution as needed, and repeatedly calls A*. We also present an extension of an existing post-smoothing technique, and show that these two techniques together produce more realistic looking paths than A*, that overcome the above limitations, while using significantly less memory and time than A*.

We propose a set of path planning tools including path generator, cost map generator, and path editor for racing games. The user can define the race by providing a racetrack as a 3D model and weights of the devised turn and heuristic functions in our system. Then, the proposed cost map generator automatically generates necessary information of the racetrack including cost map and distance to finish of any position on the race track. Different from the traditional A* problem, in our research the obstacles are dynamic and there are multiple sources and destinations. Our approach generates the path of each racer on the basis of time slots to which the path finding method applies on the fly. To further guarantee the quality of the path, we implement path smoothing using a Gaussian filter and provide an off-line path editor that allows users to edit the path in time-space domain intuitively, flexibly, and effectively. Our tools have been verified in a horse racing game to generate natural racer behaviors, demonstrating realistic and exciting racing.

A* search and its variants have been used in various fields for solving problems with large search spaces where state transitions occur because of application of operators. The key values in A* search are g(n) and h(n), where g(n) is the cost of the path from root (or start) node to node n, and h(n) is the estimated cost of cheapest path from n to goal. In this paper, we report on a space of variants of A* based on the following ideas: (i) using weighting functions for g(n) and h(n), (ii) evaluating different nodes with different heuristics, (iii) evaluating nodes with computationally cheap heuristics and re-evaluating some nodes with computationally expensive heuristics, and (iv) changing the size of the set of nodes from which the node to be expanded next is selected. We report on the bounds on the costs of solutions found by these variants of A*. We also report on the bounds for meta-variants of A* that invoke these variants sequentially. We show how the results can be used to obtain a more flexible search control without increasing the bound on the cost of the solution found by a variant or a meta-variant.

In this paper, we develop TCGD, a problem-independent, time-constrained, approximate guided depth-first search (GDFS) algorithm. The algorithm is designed to achieve the best ascertained approximation degree under a fixed time constraint. We consider only searches with finite search space and admissible heuristic functions. We study NP-hard combinatorial optimization problems with polynomial-time computable feasible solutions. For the problems studied, we observe that the execution time increases exponentially as approximation degree decreases, although anomalies may happen. The algorithms we study are evaluated by simulations using the symmetric traveling-salesperson problem.

This paper aims to present a comparative analysis of the two most utilized graph-based and sampling-based algorithms and their variants, in view of 3D UAV path planning in complex indoor environment. The findings of this analysis outline the usability of the methods and can assist future UAV path planning designers to select the best algorithm with the best parameter configuration in relation to the specific application. An extensive literature review of graph-based and sampling-based methods and their variants is first presented. The most utilized algorithms which are the A* for graph-based methods and Rapidly-Exploring Random Tree (RRT) for the sampling-based methods, are defined. A set of variants is also developed to mitigate with inherent shortcomings in the standard algorithms. All algorithms are then tested in the same scenarios and analyzed using the same performance measures. The A* algorithm generates shorter paths with respect to the RRT algorithm. The A* algorithm only explores volumes required for path generation while the RRT algorithms explore the space evenly. The A* algorithm exhibits an oscillatory behavior at different resolutions for the same scenario that is attenuated with the novel A* ripple reduction algorithm. The Multiple RRT generated longer unsmoothed paths in shorter planning times but required more smoothing over RRT. This work is the first attempt to compare graph-based and sampling-based algorithms in 3D path planning of UAVs. Furthermore, this work addresses shortcomings in both A* and RRT standard algorithms by developing a novel A* ripple reduction algorithm, a novel RRT variant and a specifically designed smoothing algorithm.

The integration of Unmanned Aerial Vehicles (UAVs) is being proposed in a spectrum of applications varying from military to civil. In these applications, UAVs are required to safely navigate in real-time in dynamic and uncertain environments. Uncertainty can be present in both the UAV itself and the environment. Through a literature study, this paper first identifies, quantifies and models different uncertainty sources using bounding shapes. Then, the UAV model, path planner parameters and four scenarios of different complexity are defined. To investigate the effect of uncertainty on path planning performance, uncertainty in obstacle position and orientation and UAV position is varied between 2% and 20% for each uncertainty source first separately and then concurrently. Results show a deterioration in path planning performance with the inclusion of both uncertainty types for all scenarios for both A* and the Rapidly-Exploring Random Tree (RRT) algorithms, especially for RRT. Faster and shorter paths with similar same success rates (>95%) result for the RRT algorithm with respect to the A* algorithm only for simple scenarios. The A* algorithm performs better than the RRT algorithm in complex scenarios.

Swarm animation is an important research direction in the field of computer animation, which aims at computer simulation of swarm behavior, real-time rendering of swarm animation and other relevant aspects. In these aspects, swarm path planning is a key issue and has received widespread attention. Some global path planning methods, such as A* and Dijkstra, due to need predefined environment information and high computation burden, is not suitable for swarm path planning; But some optimization algorithms based on swarm intelligence theory, such as particle swarm optimization (PSO), ant colony optimization (ACO) and artificial bee colony (ABC), etc. Because of its simplicity and fast convergence, has become the best choice of swarm path planning. This paper presents a multi-layer swarm path planning method. Firstly we divide the virtual environment into three layers, including geometry layer, topology layer and navigation layer. On the basis of this environmental model, the swarm path planning model is divided into inner layer and outer layer model, outer layer adopts an improved A* algorithm for topological path planning, inner layer adopts a hybrid algorithm based on ABC and PSO for dynamic path planning, then path data derived from two layers are joined together to form a final path result. Experimental results show this multi-layer swarm path planning method effectively reflected intelligence and authenticity of individuals, improved execution efficiency of the algorithm, and prevented premature convergence.