13 votes
Accepted

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

This is well covered in the corresponding chapter of Russell & Norvig (chapter 3.5, pages 93 to 99 (Third Edition)). Check that out for more details. First, let's review the definitions: Your ...
user avatar
8 votes

Are methods of exhaustive search considered to be AI?

If one thinks of intelligence as a continuous measure of optimization power (that is, how much better are outcomes for any unit of cognitive effort expended), then exhaustive search has non-zero ...
user avatar
7 votes

Are methods of exhaustive search considered to be AI?

If a computer is just brute-forcing the solution, it's not learning anything or using any kind of intelligence at all, and therefore it shouldn't be called "artificial intelligence." It has to make ...
user avatar
  • 2,559
5 votes

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

Yes. If you leave A* running (i.e. do not impose a goal condition on a newly-encountered state), all states will be explored, just as they would be in breadth- or depth- first search.
user avatar
5 votes

Is the summation of consistent heuristic functions also consistent?

No, it will not necessary be consistent or admissible. Consider this example, where $s$ is the start, $g$ is the goal, and the distance between them is 1. s --1-- g Assume that $h_0$ and $h_1$ are ...
user avatar
  • 351
4 votes
Accepted

Can two admissable heuristics not dominate each other?

This is possible. Admissibility only asserts that the heuristic will never overestimate the true cost. With that being said, it is possible for one heuristic in some cases to do better than another ...
user avatar
  • 1,016
3 votes

What are some common heuristics that might be innate?

Perhaps Occam's razor counts. Occam's razor is the meta-heuristic that "the simplest explanation is the most likely to be correct". I consider it a meta-heuristic because itself doesn't provide ...
user avatar
3 votes

What is the definition of a heuristic function in the BayesChess paper?

By far the most common form of heuristic evaluation functions for Chess-playing (or, really, any game-playing) agents are simple linear functions. At least when we're talking about handcrafted ...
user avatar
  • 9,316
3 votes

What else can boost iterative deepening with alpha-beta pruning?

First thing you're going to want to add is probably a Transposition Table, as also suggested by SmallChess. Afterwards, I'd look into Aspiration Search and/or Principal Variation Search (also see ...
user avatar
  • 9,316
3 votes
Accepted

More effective way to improve the heuristics of an AI... evolution or testing between thousands of pre-determined sets of heuristics?

Hmmm, I see some issues that are actually present in both of the approaches you propose. It is important to note that the depth level that your Minimax search process manages to reach, and therefore ...
user avatar
  • 9,316
2 votes

Are methods of exhaustive search considered to be AI?

Brute force approach is certainly the first step of many in AI programming. But using these experiences the program must learn to find the best solution or at least a closer solution to the problem. ...
user avatar
  • 51
2 votes

Are methods of exhaustive search considered to be AI?

Really any 'intelligence' exhibited by a computer is deemed AI, regardless of brute force or use of smart heuristics. For example, a chat bot can be coded to respond to most responses using many, many ...
user avatar
  • 749
2 votes

How to find proper parameter settings for a given optimization algorithm?

How to find the best configuration for an algorithm is an open research question in AI. The topic in general is known as `hyper-parameter optimization' and there are a range of possible methods: One ...
user avatar
2 votes
Accepted

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

The most obvious heuristic would indeed simply be the straight-line distance. In most cases, where you have, for example, x and y...
user avatar
  • 9,316
2 votes

What are state-of-the-art ways of using greedy heuristics to initially set the weights of a Deep Q-Network in Reinforcement Learning?

You can check out Bootstrapped DQN, with a demonstration video. Without reading much of the paper, it seems the authors use a different sampling strategy and an action-guide for specific instances. ...
user avatar
2 votes
Accepted

Is the minimum and maximum of a set of admissible and consistent heuristics also consistent and admissible?

Yes, in both cases. Below I give two very simple proofs that directly follow from the definitions of admissible and consistent heuristics. However, in a nutshell, the idea of the proofs is that $h_{\...
user avatar
  • 33k
2 votes

How do I find whether this heuristic is or not admissible and consistent?

Welcome to AI.SE @hpr16! Your understanding of when a heuristic is admissible is correct, but your heuristic is inadmissible. An admissible heuristic must always underestimate the cost to move from a ...
user avatar
2 votes

What is the definition of a heuristic function in the BayesChess paper?

Heuristics can be understood aas rules. Typically heuristics are thought of as problem-specific strategies. Expert systems were an early form of AI that utilized rules-based decisions. In a game-...
user avatar
  • 6,077
2 votes

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

If by "visit multiple targets", you mean "visit several points in the fastest order", you are no longer in a simple path-finding-style search problem, but instead in an optimization problem. This is ...
user avatar
2 votes

Understanding the proof that A* search is optimal

The key phrase here is because heuristics are admissible In other words, the heuristics never overestimate the path length: $$cost(n) + heuristic(n) \le cost(\text{any path going through n})$$ And ...
user avatar
1 vote

A* is similar to Dijkstra with reduced cost

What you are doing when calculating $d'(x,y)$: $d(x,y)$: calculating the original edge distance from $x$ to $y$ $h(y)$: plus the heuristic from $y$ to the goal $h(x)$: minus the heuristic from $x$ to ...
user avatar
1 vote
Accepted

Why is the effective branching factor used for measuring performance of a heuristic function?

I also walked into that trap the first few times. The difference is the following: $N$ is the number of expanded nodes $b^*$ is the effective branching factor $b^*$ depends on the depth $d$ of the ...
user avatar
  • 126
1 vote

Why is the effective branching factor used for measuring performance of a heuristic function?

As you found $N$ is the number of nodes that are expanded. The cost of expansion of each node is equal to the number of children of that node. Hence, we use $b^*$ for each node. In other words, the ...
user avatar
  • 1,663
1 vote
Accepted

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

Question 1: First of all, you state that that the goal G2 will be found first by relying on the expansion order R, B, D, G2. This is wrong. It is extremely easy to ...
user avatar
1 vote

What else can boost iterative deepening with alpha-beta pruning?

Try cache or transposition table. Without it, your search tree might explode.
user avatar
  • 1,368
1 vote

What else can boost iterative deepening with alpha-beta pruning?

To make boost iterative deepening with alpha-beta pruning you can use the SSS* Search algorithm, its a best first strategy algorithm. The SSS* Algorithm can improve the time efficiency of the overall ...
user avatar
  • 11
1 vote

Strategic planning and multi dimensional knapsack problem

Here is a speculative cast of the problem to a travelling salesman problem, which would lead to shortest-path algorithms. Please note this idea suggests different constraints to explore. Given the ...
user avatar
  • 1,480
1 vote
Accepted

Is a subset of a problem solution, used to recreate complete solution considered a heuristic?

Since you mention the A* algorithm, then you are definitely using a heuristic somewhere in there, at least with the A* algorithm while solving the subproblems using the straight-line distance as your ...
user avatar
1 vote

Is a subset of a problem solution, used to recreate complete solution considered a heuristic?

A 'heuristic' is simply a 'rule-of-thumb', i.e. something which doesn't guarantee an optimal solution to a problem. Beyond the above notion (certainly within the discipline of optimization), the ...
user avatar
1 vote

Is a subset of a problem solution, used to recreate complete solution considered a heuristic?

Whether or not a label fits any particular instance depends on what you're using the label for. If something specific is riding on whether this approach is a 'heuristic' or not, that context is ...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible