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 ...
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 ...
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 ...
  • 2,569
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.
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 ...
  • 361
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 ...
  • 1,026
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 ...
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 ...
  • 9,509
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 ...
  • 9,509
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 ...
  • 9,509
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. ...
  • 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 ...
  • 809
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 ...
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...
  • 9,509
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. ...
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_{\...
  • 34.9k
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 ...
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-...
  • 6,107
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 ...
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 ...
1 vote

Why aren’t heuristics for Connect Four Monte Carlo tree search improving the agent?

It might be the case that if you perform a large number of random rollouts, the "best action" as chosen by the agent without the domain knowledge, is same as the agent with the domain knowledge. I ...
  • 313
1 vote

Agents meeting in a directed connected graph

It's not possible to solve version 1) of the problem in general. To see why, consider a graph with 2 cities, and 2 agents, where the agents start in opposite nodes. Since both agents need to move ...
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 ...
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 ...
1 vote

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

Try cache or transposition table. Without it, your search tree might explode.
  • 1,390
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 ...
  • 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 ...
  • 1,490
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 ...
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 ...
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 ...

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