Questions tagged [a-star-search]
The a-star-search tag has no usage guidance.
17
questions
3
votes
0
answers
22
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
2
votes
1
answer
82
views
D* Lite - can edge costs be asymmetric?
I'm trying to modify the original D* Lite algorithm adding a margin constraint wrt to any nearby obstacle to be satisfied for each selected cell in the path. This causes the edge cost function between ...
- 145
0
votes
0
answers
8
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
2
answers
121
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 ...
- 13
0
votes
1
answer
126
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 ...
- 21
3
votes
1
answer
152
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 ...
- 133
2
votes
0
answers
37
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 ...
- 151
0
votes
1
answer
37
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 --...
- 131
2
votes
0
answers
3k
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,...
- 391
0
votes
2
answers
542
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 ...
- 582
0
votes
1
answer
176
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 ...
- 582
2
votes
2
answers
1k
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 ...
- 21
2
votes
2
answers
54
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 ...
- 123
2
votes
0
answers
68
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
0
votes
0
answers
498
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
1
answer
49
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 ...
- 241
2
votes
2
answers
409
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?
- 310