8

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 definitions of admissible and consistent are correct. An admissible heuristic is basically just "optimistic". It never overestimates a distance. A consistent ...


8

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 intelligence (in that it does actually give better outcomes as more effort is expended) but very, very low intelligence (as the outcomes are better mostly by luck, ...


7

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 decisions based on what's happened before in similar instances. For something to be intelligent, it needs a way to keep track of what it's learned. A chess ...


5

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

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 perfect heuristics. Then $h_0(s) = 1$ and $h_1(s) = 1$. In this case the heuristic is inadmissible because $h_0(s)+h_1(s) = 2 > d(s, g)$. Similarly, as an ...


4

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 and vice-versa. Think of it as a game of rock paper scissors. Specifically, you may find that sometimes $h_1 < h_2$ and in other times $h_2 < h_1$, where $...


3

You may start assigning penalties for undesirable conditions in a state like: 1) Number of blocks outside stack 0. Supose you penalize with 10 units each block outside stack 0, then the starting state above adds 40 units to the penalty score 2) Number of blocks in the stack 0 in a position different than in the goal state. Supose you penalize with 50 ...


3

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 explanations, only means of comparing them among another. It is a heuristic because like all heuristics, it can lead to false conclusions, but is usually right.


2

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 if statements. This is an AI no matter how poorly coded/designed it is. The chess playing computer beating a human professional can be seen as a meaningful ...


2

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 of the most popular is IRace, but other possibilities include: Spearmint: uses wrappers in Matlab or Python. It uses MongoDb, and Bayesian optimisation ...


2

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. Another way to initially set weights for the network is to create a dataset of moves (correct, incorrect, etc, as long as they are relevant) and have the network ...


2

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 roughly the difference between chapters 3 & 6 of Russell & Norvig's section on search. To do this, you can't just change your heuristic, instead you ...


2

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 also the speed with which it can traverse the tree, is extremely important for the algorithm's performance. Therefore, when evaluating how good or bad a ...


2

The most obvious heuristic would indeed simply be the straight-line distance. In most cases, where you have, for example, x and y coordinates for all the nodes in your graph, that would be extremely easy to compute. The straight-line distance also fits the requirements of an admissible heuristic, in that it will never overestimate the distance. The travel-...


2

In theory it is quite an accomplishment during those times , but the main reason GPS works is because the problems should be described in a "well formed format". And it is near impossible to formulate real world problems in that manner (image classification , speech recognition etc).


2

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 since the frontier is ordered by $\textbf{cost + heuristic}$, when a completed path $p$ is dequeued from the frontier, we know that it must necessarily be $\...


2

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_{\max}(n)$ and $h_{\min}(n)$ are, by definition (of $h_{\max}$ and $h_{\min}$), equal to one of the given admissible (or consistent) heuristics, for all nodes $n$, ...


2

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 given state to a goal state. Notice that states in the search are not the same as positions on the circle in your problem. A state needs to capture all the ...


2

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. Since the first goal in AI is to find any solution, nothing can beat the brute force approach. But then using the previous results of brute force approaches, the ...


2

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 features that's the case, of course all the hype with Deep Neural Networks in more recent years is different. So, when it's not specified in a paper like this exactly ...


1

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-playing context, heuristics can be pure strategies. A heuristic function would be one that includes a some predefined decision rules. Russell and Norvig have a ...


1

I will use the 8-puzzle game to show you why Nilson's sequence score heuristic function is not admissible. In the 8-puzzle game, you have a $3 \times 3$ board of (numbered) squares as follows. +---+---+---+ | 0 | 1 | 2 | +---+---+---+ | 7 | 8 | 3 | +---+---+---+ | 6 | 5 | 4 | +---+---+---+ The numbers in these squares are just used to refer to the ...


1

Based on your description, I'd maximize the following terms: i -max(f - 10 - (MAX_FIELD_INDEX - i), 0) - assuming consumption of one fuel per field; this becomes negative when you have too much fuel a similar function of p, as spending them gets more important when approaching the goal As having fuel is probably a good thing in the beginning, you could use ...


1

If you have the best combination of distance between the stones, you should choose the best move to win. In this case, you have to be close to where your opponent plays. It is best to do this by surrounding your opponent's stones. You should always put the first stone in middle or corner of the table.


1

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 knowledge vectors and efforts, build a acyclic directed graph (acyclic, as we are not supposed to unlearn). A vertex is an article, represented by its knowledge ...


1

I wrote some python code to reproduce this paper's purported results. My code very efficiently optimizes simple smooth functions like bowls, but does not come close to reproducing the paper's claimed results on more complex functions, including with the parameters the authors report. I think that, since both @Jairo and I were unable to reproduce the results ...


1

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 see that this is wrong, because A* is a search algorithm that guarantees to find an optimal solution given that only admissible heuristics are used. (A heuristic is being admissible if it never ...


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