China
Africa
Explore chapters and articles related to this topic
A Constraint Programming Solution for the Military Unit Path Finding Problem
Published in Jitendra R. Raol, Ajith K. Gopal, Mobile Intelligent Autonomous Systems, 2016
Louise Leenen, Alexander Terlunen, Herman le Roux
A significant volume of research has been done on path finding techniques, and the success of a particular technique relies on the environment and the constraints that are imposed on it. In this chapter, the scope is limited to a domain where a military unit has to move, or be moved, safely to a destination while avoiding obstacles such as threats and structures. We assume that the terrain can be presented as a two-dimensional grid or a graph. Tarapatta [4] gives an overview of techniques for terrain representation. The most common approaches to solving path finding problems are based on Dijkstra’s shortest path algorithm and the A* search algorithm. The A* search algorithm is a graph-based algorithm that finds the least cost path between a source and destination node by minimising the estimated cost to the goal from the current node, as well as the cost of the path so far. This algorithm is regarded as one of the most efficient graph-based path finding algorithms. A* search-based algorithms are used in most electronic games for path finding. A* search is a heuristic, optimal algorithm and also optimally efficient, that is, at least as efficient in terms of node expansion as any other optimal algorithm [5]. The choice of a heuristic function is very important. A* search is optimal if the heuristic function never overestimates the minimum cost from a node n to the destination node. Common heuristic functions are the Manhattan or Euclidean distance. One of the disadvantages of the A* search algorithm is that it requires a large amount of memory space. Path finding on large maps can be problematic but many extensions of the algorithm address this deficiency by reducing search space, and time and memory requirements. The A* search algorithm is formulated for static environments but there is an extension, the D* algorithm, that is designed for dynamic environments. We discuss this algorithm in more depth later on.
A* Search and Some Admissible Heuristics for It
Published in Don Potter, Manton Matthews, Moonis Ali, Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, 2020
Antti Autere, Johannes Lehtinen
In brief, A* is an ordered best-first search algorithm that always examines the successors of the “most promising” node based on the function: f(n) = g(n) + h(n), where g(n) is the length of the shortest path from the starting node to n. The heuristic, h(n), is an estimate of the length of the shortest path from n to amy goal node.
Piping auto-routing using key-node generation method in ships
Published in Ships and Offshore Structures, 2022
Youngsu Kim, Kyungho Lee, Yangwook Kim, Youngsoo Han, Byeongwook Nam, Hyunbin Yeo
The A* algorithm is a graph search algorithm that determines the path from the initial node to the target node, uses a heuristic strategy for estimating the best path value from the node to the destination at each node, and searches the nodes in the order of these heuristic estimates. Thus, this algorithm is a type of best-first search method with an internal priority queue sorted according to the least cost and determines the search order from it. A feature of the A* algorithm is that it uses a heuristic strategy, which estimates the cost from the target node to the last point. The cost estimate of the A* algorithm is expressed in Equation (5).
Automatic computation of bending sequences for wire bending machines
Published in International Journal of Computer Integrated Manufacturing, 2022
Andrea Baraldo, Luca Bascetta, Fabrizio Caprotti, Sumit Chourasiya, Gianni Ferretti, Angelo Ponti, Basak Sakcak
A* is a search algorithm (Hart, Nilsson, and Raphael 1968) that determines the shortest path between a start and a goal node in a graph. It is one of the most popular technique used in graph traversals, due to its completeness, optimality, and efficiency. A* algorithm, unlike other traversal techniques, is a smart algorithm that determines the successive node based not only on the cost to reach the current node, but also anticipating the cost to reach the goal from thereon, by way of a problem-dependent heuristic function.