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 ...
- 9,207
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 ...
- 4,262
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,589
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.
- 7,226
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 ...
- 371
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,106
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 ...
- 2,071
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 ...
- 10.1k
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 ...
- 10.1k
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 ...
- 10.1k
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 ...
- 823
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 ...
- 7,226
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...
- 10.1k
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.
...
- 906
2
votes
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 ...
- 210
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_{\...
- 39.7k
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 ...
- 9,207
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,237
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 ...
- 9,207
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 ...
2
votes
Is A* with an admissible but inconsistent heuristic optimal?
It depends on what you mean by optimal.
A* will always find the optimal solution (that is, the algorithm is admissible) as long as the heuristic is admissible. (Note that the definition of admissible ...
- 371
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 ...
- 333
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 ...
- 9,207
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,011
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,411
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 ...
- 56
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 ...
- 7,226
Only top scored, non community-wiki answers of a minimum length are eligible