China
Africa
Explore chapters and articles related to this topic
Path Planning and Optimization
Published in Amit Kumar Tyagi, Niladhuri Sreenath, Handbook of Research of Internet of Things and Cyber-Physical Systems, 2022
Pranjal Paul, G. Venkata Krishna, Arpit Jain
A* algorithm is a variation of the best-first search heuristic technique. It is an easy to apply technique with good results in known environments. Here, the search space or map is divided into a grid with each cell denoted as a node. Once the start and end position of the robot is determined, the cost function of each adjacent node to reach the end position is calculated. The cost function f (n) is given by: f(n)=g(n)+h(n) where; n is the node under consideration; g(n) is the cost to move to n$$$$$th node from the current position; h(n) is the estimated cost to move from nth node to the end position.
Problem Solving by Intelligent Search
Published in Konar Amit, Artificial Intelligence and Soft Computing, 2018
Heuristic search is generally employed for two distinct types of problems: i) forward reasoning and ii) backward reasoning. We have already discussed that in a forward reasoning problem we move towards the goal state from a pre-defined starting state, while in a backward reasoning problem, we move towards the starting state from the given goal. The former class of search algorithms, when realized with heuristic functions, is generally called heuristic Search for OR-graphs or the Best First search Algorithms. It may be noted that the best first search is a class of algorithms, and depending on the variation of the performance measuring function it is differently named. One typical member of this class is the algorithm A*. On the other hand, the heuristic backward reasoning algorithms are generally called AND-OR graph search algorithms and one ideal member of this class of algorithms is the AO* algorithm. We will start this section with the best first search algorithm.
Estimation of Routing Congestion
Published in Charles J. Alpert, Dinesh P. Mehta, Sachin S. Sapatnekar, Handbook of Algorithms for Physical Design Automation, 2008
Rupesh S. Shelar, Prashant Saxena
The standard breadth-first search used in global routers is based on Dijkstra’s shortest path algorithm. This algorithm can be sped up significantly during the congestion estimation mode by applying fast search techniques such as best-first search and A* search [HNR68]. These techniques rely on being able to estimate the distance to the destination, and are therefore not always easily applicable during the regular global routing process (because it may be difficult to estimate the cost of the unexplored portion of a route if the cost function includes components for delay or congestion). In contrast, the cost function used for routing during the congestion estimation mode is almost always the wirelength, which can be approximated at any arbitrary bin by the Manhattan distance between that bin and the destination bin. The difference between the A* search and best-first search techniques is that A* considers the cost from the source as well as distance to the destination while expanding the search wavefront, in contrast to best-first search, which expands at a bin that is closest to the destination. Although the asymptotic time complexity of both best-first search and A* search is same as that of breadth-first search, they offer significant speed-up in practice, because they usually visit fewer nodes while finding a route. For example, as shown in Figure 30.3, breadth-first search visits twelve nodes while finding a route from bin s to bin t, whereas best-first search and A* search can do so by visiting only seven and nine bins, respectively.
Inverse reinforcement learning-based time-dependent A* planner for human-aware robot navigation with local vision
Published in Advanced Robotics, 2020
Shiying Sun, Xiaoguang Zhao, Qianzhong Li, Min Tan
The A* algorithm integrates the characteristics of the best-first search (BFS) algorithm and Dijkstra algorithm [26] to use a graph search method to search for an optimal path. The evaluation function of the A* algorithm is given by: where denotes the cost function of the robot from initial state to current state s, represents the estimated distance (heuristic function) from current state s to the target position.
Improving Domain-Independent Heuristic State-Space Planning via plan cost predictions
Published in Journal of Experimental & Theoretical Artificial Intelligence, 2023
Francesco Percassi, Alfonso E. Gerevini, Enrico Scala, Ivan Serina, Mauro Vallati
A well-established approach to solving planning tasks is forward heuristic search over a transition system induced by the grounding of .1 That is, start from the initial state, and navigate the state space by the domain actions applied using a best-first search policy until a goal state is found. Best-first search usually organises the exploration by expanding from a frontier the node that minimises a given function . Let be the length or the plan cost of the prefix leading to node , a heuristic function predicting the remaining cost to get to the goal, and a constant weight. With the best-first search becomes the well known weighted A* algorithm (Pohl, 1970). A critical aspect in such a setting is to devise a heuristic that well balances the precision of the estimating the actual distance to the goal () and its computational cost. A popular way to devise a suitable heuristic function for a STRIPS problem is by exploiting its delete-free relaxation. The delete-free relaxation of a STRIPS Problem is a new STRIPS problem which is identical to except that all the actions have empty negative effects. This relaxation has been proved effective to devise heuristics with a good trade-off between precision and computational cost. Several delete-free relaxation heuristics have been defined in the literature (e.g., (Bonet & Geffner, 2001; Domshlak et al., 2015; Hoffmann & Nebel, 2001)), but for the scope of this work it is only important to discern when such heuristics are admissible and when they are not. A heuristic is said to be admissible if it does not overestimate the actual solution cost, inadmissible otherwise. Admissible heuristics with can be used to make A* always produce an optimal solution; inadmissible heuristics trade this admissibility for more information of the relaxed problem, and some of them are quite convenient approximations from a practical standpoint, especially when optimality is not a major concern. In this work, we will use three heuristics, all exploiting the delete-free relaxation principle: (Bonet & Geffner, 2001), (Hoffmann & Nebel, 2001) and (Richter & Westphal, 2010). is admissible, while both and only provide inadmissible estimates.