# Questions tagged [a-star-search]

The tag has no usage guidance.

12 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
106 views

### A* (A-star) path finding in continuous environments with "sticky slower" areas

I have a search problem, finding the shortest path for 3 vehicles to their parking spots, in a continuous environment (inputs are continuous for velocity, turn speed) and the location is continuous, ...
• 207
46 views

### Finding multiple paths through a grid such that every grid square is equally used

Setup Here’s the setup: I have an $N$ x $N$ grid of tiles, and a list of $M$ agents that need to move across the grid. Each agent has its own start tile $S(a)$, end tile $E(a)$, and an exact number ...
5k views

### Comparing classical tree-search algorithms (BFS,DFS,A*,IDS) - when to use one or the other?

I have a question about classical tree-search algorithms as I will have an exam soon and this is the type of questions they might be asking. Although I know how to compare the complexities, optimality,...
• 401
75 views

### Heuristic for searching for solutions on an 8-puzzle variant with non-unique tiles

I'm trying to perform an A* search on a particular N-puzzle variant in which some tiles are identical. More specifically, assuming an $m \times m$ grid, there are m colors with m tiles of each. The ...
• 151
1 vote
80 views

### Simplified Memory Bounded A*

I have been studying the SMA* algorithm and I am having trouble understanding the backup operation. Specifically, I don't understand why the f value of a child node should be the maximum of its own f ...
1 vote
93 views

### Optimality of A* algorithm

In the book Artificial Intelligence a Modern Approach 4th edition, the author claims that the A* algorithm is cost-optimal if the heuristic function is ...
• 111
1 vote
115 views

### A* pseudocode problem

What is the difference between this two pseudocode and which one should i implement? ...
26 views

### A* (A-star) search algorithm including closest distance from a node to an obstacle in heuristic and step cost

I want to include the distance of a node to the closest obstacle in the cost function, so that the path length is not only minimal, but also not near obstacles. We know that: Dijkstra's algorithm uses ...
119 views

### How to avoid costly square root operations in A* algorithm?

As a reminder, in an A* algorithm, vertices in the priority queue are sorted according to their priority $f = g + h$, where $g$ is the cost of getting to this vertex from the start vertex, and $h$ is ...
• 737
71 views

### How is this "pathmax modification," $f(n^\prime) = \max(g(n^\prime) + h(n^\prime), f(n))$, useful?

I am studying the concept of heuristics in search algorithms, and the $A^*$ search algorithm in particular. I am told the following: Greedy search minimises estimated path-cost to goal. But it's ...
• 203