Questions tagged [a-star-search]
The a-star-search tag has no usage guidance.
17
questions
0
votes
0answers
7 views
Separating Axis Theorem for Obstacle Detection
I'm currently working on a Robotics project. The project objective is to create a nonholonomic robot path finding algorithm to be integrated into an actual STM Controller. I am currently stuck at ...
1
vote
2answers
93 views
Should your heuristic for an A* search algorithm be the same scale as your actual weights?
I'm a bit confused about the scale of heuristics for implementing A* search. $f(n)$ is the total cost of travelling to a node $n$. It is calculated by $f(n) = g(n) + h(n)$. $g(n)$ is the cost of the ...
0
votes
0answers
43 views
A* search tree version - Can a node be in the frontier multiple times
I took an exam today and it had a question on A* tree search version, we only briefly skimmed over this on the material, focusing more on the graph search version.
In the example in the question text ...
0
votes
0answers
14 views
What's the best way to combine multiple A* searches?
I have a graph that looks like this
The highlights nodes must be visited, and the blue node must be visited last, the stickman must be the start of the path. The weights are the Euclidean distance ...
0
votes
1answer
88 views
Using A* path finding is giving me inaccurate results
So I am using A* pathfinding to find a path from a person, to a node on a graph. This person has a few 'must pass' nodes that they must go through. So my solution was to run the algorithm for each of ...
3
votes
1answer
114 views
Are there graphs for which A* cannot be admissible?
Wikipedia states that "On infinite graphs with a finite branching factor and edge costs that are bounded away from zero $ (d(x,y)>\varepsilon >0$ for some fixed $\varepsilon$), A* is guaranteed ...
2
votes
0answers
34 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 ...
0
votes
1answer
30 views
Why doesn't A* give the optimal path for navigating from A to R in this state space?
Well, I have heard that the A* algorithm is optimal and complete. However, when trying to navigate from A to R using A*, it outputs the path, A --> E --> R, although there is a shorter path, A --> M --...
2
votes
0answers
2k 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,...
0
votes
2answers
400 views
Coefficients in cost function in A-star
I'd like to expand on this question :
https://stackoverflow.com/questions/52420788/why-does-the-a-star-algorithm-need-gn
Dijkstra's algorithm uses cost function $f(n) = g(n)$
whereas A* uses cost ...
0
votes
1answer
133 views
Can Dijkstra's algorithm outperform A star, in terms of vertices checked?
I know Dijkstra's algorithm can be seen as a specific case of A star, when the estimation heuristic used simply returns 0, so I know that A star with this specific heuristic can not check more ...
2
votes
2answers
788 views
A* without heuristic more efficient than Dijkstra
I am using the module networkx to operate on graphs made from OpenStreetMap.
I wanted to compare the shortest path algorithm to ...
2
votes
2answers
50 views
cheap multi agent path planning algorithms
I am trying to make a tower defence game where some critters are trying to make their ways through a 2D grid-like obstacle course. The idea is these critters cannot walk into the obstacles or into ...
2
votes
0answers
51 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 ...
0
votes
0answers
410 views
How can an A* algorithm visit all nodes?
Is it possible to find the shortest path and visit all the nodes in a graph by A* algorithm? If yes, how?
0
votes
1answer
34 views
Term for an A*-like pathfinding strategy where only the heuristic goal distance matters
I am trying to find a proper term for the A*-like best-first pathfinding strategy where the node to expand next is the one with the least estimated distance from the goal, regardless of its distance ...
2
votes
2answers
283 views
Does an optimal path imply the heuristic is admissible?
If we are given an A$^*$ path search with some heuristic $h$ that yields an optimal path, without knowing that the heuristic is admissible beforehand, would this imply that $h$ is admissible?
