Skip to main content

Questions tagged [a-star]

For questions related to the A* (or A) search algorithm, which is a very famous state-space search algorithm and widely taught in Computer Science and Artificial Intelligence. A* is a best-first search algorithm that is guaranteed to find the optimal solution given an admissible heuristic function, so A* is also an informed search algorithm, as opposed to e.g. depth-first search, which is an uninformed search algorithm.

Filter by
Sorted by
Tagged with
0 votes
1 answer
90 views

How do we know that $c(n,a,G) = h^{\ast}(n)$, in the proof that if a heuristic is consistent then it is admissible?

I found a proof that if a heuristic $h$ is consistent, then it is admissible, but I'm confused by one of the steps in the proof. The proof is by induction on $k$, the number of actions from a node $n$ ...
Hugh Mann's user avatar
0 votes
1 answer
72 views

Which search algorithm expands nodes closest to the goal?

I want to know which search algorithm among A* and Best-First Search and Greedy First Search expands nodes closest to the goal. I have three opinions about A* and Best-First Search and Greedy First ...
ndycuong's user avatar
0 votes
0 answers
106 views

How do I construct a state space that shows that Greedy Best First Search is not complete while A* is?

Construct a state space with appropriate heuristics and local costs. Show that Greedy Best First search is not complete for the state space. Also illustrate A* is complete and guarantees solution for ...
npsulav's user avatar
0 votes
0 answers
112 views

What is a good algorithm (and a heuristic) to find the shortest path in a puzzle game?

In a 3D world, there is a Robot, boxes, and switches. The robot's job is to carry boxes (one box at a time) and put them on top of switches to solve the level. All switches must have a box on top for ...
Arcane's user avatar
  • 1
0 votes
2 answers
2k views

What does consistency of heuristic intuitively mean in the A* algorithm and why are consistent heuristics monotonic?

Could someone give the intuition behind consistency of heuristic function in the A* algorithm? From wikipedia: Every node i will give an estimate that, after accounting for the cost to reach i + 1, ...
learner's user avatar
  • 13
1 vote
0 answers
126 views

Is N the total number of nodes in the frontier plus the number of nodes in the explored list?

I'm studying fundamentals of AI from the classic Russell-Norvig book (3rd edition). I have a small doubt about the effective branching factor, which is defined as follows (section 3.6.1, p. 103): One ...
Baffo rasta's user avatar
0 votes
1 answer
537 views

Where can I find Norvig's version of the pseudocode for the A* search algorithm?

Can anybody point me to a link to Peter Norvig's version of the A* pseudocode. I've googled it interminably but found nothing. It's the version that uses the Unexplored/Frontier/Explored data ...
Fred Friendly's user avatar
0 votes
0 answers
263 views

Is possible to perform an early goal test with A* using a consistent heuristic?

I have a doubt about A* goal test. As far as I know an early goal test is performed when a node (representing a certain state) is inserted in the frontier or, to conform with AIMA terminology, when is ...
InCrisis's user avatar
3 votes
1 answer
204 views

Is there an error in A* optimality proof Russel-Norvig 4th edition?

In "AI: A Modern Approach", 4th edition, by Russell and Norvig, they give a purported proof that A* is cost-optimal for any admissible heuristic. The given proof seems most certainly wrong. ...
vdbuss's user avatar
  • 81
0 votes
0 answers
202 views

Comparing heuristics in A* search and rescue operation

I was reading a research paper titled A Comparative Study of A-star Algorithms for Search and rescue in Perfect Maze (2011). I have some doubts regarding it: 1. The Evaluation Function of $\mathrm{A}^...
user46328's user avatar
2 votes
1 answer
369 views

If $h_1(n)$ is admissible, why does A* tree search with $h_2(n) = 3h_1(n)$ return a path that is at most thrice as long as the optimal path?

Consider a heuristic function $h_2(n) = 3h_1(n)$. Where $h_1(n)$ is admissible. Why are the following statements true? $A^*$ tree search with $h_2(n)$ will return a path that is at most thrice as ...
Jia Rong's user avatar
1 vote
2 answers
2k views

Is there any situation in which breadth-first search is preferable over A*?

Is there any situation in which breadth-first search is preferable over A*?
JackoJackie's user avatar
0 votes
0 answers
44 views

Incorrect node expansion in game board with A* search

I have the following game board below, and we're using A* search to find the optimal path from the agent to the key. There are 8 directions. Up, down, left, right have a cost of 1, and diagonal ...
Manny's user avatar
  • 21
1 vote
1 answer
2k views

What is the difference between the heuristic function and the evaluation function in A*?

I am reading college notes on state search space. The notes (which are not publicly available) say: To do state-search space, the strategy involves two parts: defining a heuristic function, and ...
Slowat_Kela's user avatar
2 votes
0 answers
643 views

Why do we use the tree-search version of breadth-first search or A*?

In Artificial Intelligence A Modern Approach, search algorithms are divided into tree-search version and graph-search version, where the graph-search version keeps an extra explored set to avoid ...
Gu Liqi's user avatar
  • 21
3 votes
1 answer
3k views

What are the differences between Q-Learning and A*?

Q-learning seems to be related to A*. I am wondering if there are (and what are) the differences between them.
Gonçalo Peres's user avatar
3 votes
1 answer
3k views

Is A* with an admissible but inconsistent heuristic optimal?

I understand that, in tree search, an admissible heuristic implies that $A*$ is optimal. The intuitive way I think about this is as follows: Let $P$ and $Q$ be two costs from any respective nodes $p$ ...
Harry Stuart's user avatar
1 vote
1 answer
1k views

Which heuristics guarantee the optimality of A*?

The following is a statement and I am trying to figure out if it's true or false and why. Given a non-admissible heuristic function, A* will always give a solution if one exists, but there is no ...
ndrb's user avatar
  • 25
1 vote
1 answer
127 views

Doesn't the number of explored nodes with IDA* increase linearly?

I think I'm misunderstanding the description of IDA* and want to clarify. IDA* works as follows (quoting from Wiki): At each iteration, perform a depth-first search, cutting off a branch when its ...
Edward Garemo's user avatar
2 votes
0 answers
134 views

How does heuristic work with multiple agents?

I have a question for heuristic search with multiple agents. I know how heuristic search works with one agent (ex. one Pacman) but I don't really understand it with multiple agents. Let's say we have ...
anthino12's user avatar
  • 121
1 vote
1 answer
506 views

What does a consistent heuristic become if an edge is removed in A*?

For the A* algorithm, a consistent heuristic is defined as follows: if, for every node $n$ and every successor $m$ of $n$ generated by any action $a$, $h(n) \leq c(n,m) + h(m)$. Suppose the edge $c(...
calveeen's user avatar
  • 1,261
3 votes
1 answer
1k views

A* and uniform-cost search are apparently incomplete

Consider the following diagram of a graph representing a search space. If we start at $B$ and try to reach goal state $E$, the lowest-cost first search (LCFS) (aka uniform-cost search) algorithm ...
KGhatak's user avatar
  • 165
2 votes
0 answers
120 views

How can I assign agents to tasks based on time and affinity?

I am working on an assignment problem. Consider $K$ agents $A_1, \dots A_K$ and $N$ tasks $T_1, \dots T_N$. Each task has a certain time $t(T_i)$ to be completed and each agent has a matching (or ...
Tariq Kavish Arain's user avatar
2 votes
1 answer
1k views

In the graph search version of A*, can I stop the search the first time I encounter the goal node?

I am going through Russel and Norvig's Artificial Intelligence: A Modern Approach (3rd edition). I was reading the part regarding the A* algorithm A* graph search version is optimal when heuristic ...
Fenil's user avatar
  • 181
7 votes
1 answer
2k views

How do we determine whether a heuristic function is better than another?

I am trying to solve a maze puzzle using the A* algorithm. I am trying to analyze the algorithm based on different applicable heuristic functions. Currently, I explored the Manhattan and Euclidean ...
m2rik's user avatar
  • 333
2 votes
1 answer
3k views

Understanding the proof that A* search is optimal

I don't understand the proof that $A^*$ is optimal. The proof is by contradiction: Assume $A^*$ returns $p$ but there exists a $p'$ that is cheaper. When $p$ is chosen from the frontier, assume $...
Gooby's user avatar
  • 351
7 votes
1 answer
372 views

A* is similar to Dijkstra with reduced cost

According to this Wikipedia article If the heuristic $h$ satisfies the additional condition $h(x) \leq d(x, y) + h(y)$ for every edge $(x, y)$ of the graph (where $d$ denotes the length of that edge),...
Shrey Shrivastava's user avatar
-1 votes
2 answers
3k views

How can the A* algorithm be optimized?

How can the A* algorithm be optimized? Any references that shows the optimization of A* algorithm are also appreciated.
Lexi's user avatar
  • 109
1 vote
1 answer
261 views

How can I calculate the shortest path between two 2d vector points in an environment with obstacles?

I have a 2D plane, with a fixed height and width of 10M. The plane has an agent (or robot) in the point $(1, 2.2)$, and an electric outlet in the point $(8.2, 9.1)$. The plane has a series of ...
Tlaloc-ES's user avatar
  • 113
1 vote
1 answer
178 views

What kind of search method is A*?

What kind of search method is A*? Explain to me with an example.
Maira Khan's user avatar
5 votes
1 answer
13k views

How do I show that uniform-cost search is a special case of A*?

How do I show that uniform-cost search is a special case of A*? How do I prove this?
dua fatima's user avatar
2 votes
1 answer
113 views

How is the cost of the path to each node computed in A*?

How is the cost of the path to each node $n$ computed in the A* algorithm? Do we need to add the cost of the path to the parent node $p$ to the cost of the path of the child node $n$?
Jazba's user avatar
  • 31
14 votes
3 answers
65k views

What are the differences between A* and greedy best-first search?

What are the differences between the A* algorithm and the greedy best-first search algorithm? Which one should I use? Which algorithm is the better one, and why?
Marosh Fatima's user avatar
6 votes
1 answer
14k views

How is iterative deepening A* better than A*?

The iterative deepening A* search is an algorithm that can find the shortest path between a designated start node and any member of a set of goals. The A* algorithm evaluates nodes by combining the ...
Huma Qaseem's user avatar
3 votes
3 answers
9k views

What heuristic to use when doing A* search with multiple targets? [closed]

Usually, using the Manhattan distance as a heuristic function is enough when we do an A* search with one target. However, it seems like for multiple goals, this is not the most useful way. Which ...
dragan's user avatar
  • 31
0 votes
1 answer
10k views

How do you calculate the heuristic value in this specific case?

The A* algorithm uses the "evaluation function" $f(n) = g(n) + h(n)$, where $g(n)$ = cost of the path from the start node to node $n$ $h(n)$ = estimated cost of the cheapest path from $n$ to the ...
Surya Bhusal's user avatar
13 votes
1 answer
29k views

Why is A* optimal if the heuristic function is admissible?

A heuristic is admissible if it never overestimates the true cost to reach the goal node from $n$. If a heuristic is consistent, then the heuristic value of $n$ is never greater than the cost of its ...
Wizard's user avatar
  • 303
4 votes
1 answer
4k views

What is a good heuristic function for A* to solve the "blocks world" game?

I am developing a heuristic solution for the blocks world problem. I tried using the number of blocks out of place as my $h(n)$. It seems a little ineffective. Can someone please point out a suitable ...
user3758749's user avatar
6 votes
2 answers
2k views

How does A* search work given there are multiple goal states?

When I have read through the fundamentals of AI, I saw a situation (i.e., a search space) which is illustrated in the following picture. These are the heuristic estimates: ...
hellojoshhhy's user avatar