Artificial Intelligence Stack Exchange
Artificial Intelligence Stack Exchange

Questions tagged [heuristics]

In AI, the term "heuristic" is used in the context of non-blind (i.e., informed) search and planning: the problem of finding a sequence of actions to find/generate a desired state from an initial state. Heuristics" are problem relaxations of the original problem. They get as input the current state/search node and output the cost of the relaxed solution from there to goal. This heuristic value is then used for search guidance.

46 questions
14
votes
1 answer

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 successor, $n'$, plus the successor's heuristic…
Wizard
  • 313
  • 1
  • 2
  • 6
12
votes
5 answers

Are methods of exhaustive search considered to be AI?

Some programs do exhaustive searches for a solution while others do heuristic searches for a similar answer. For example, in chess, the search for the best next move tends to be more exhaustive in nature whereas, in Go, the search for the best next…
WilliamKF
  • 2,533
  • 1
  • 26
  • 31
12
votes
1 answer

Strategic planning and multi dimensional knapsack problem

I'm trying to find a planning approach to solve a problem that attempts to model learning of new material. We assume that we only have one resource such as Wikipedia, which contains a list of articles represented as a vector of knowledge it contains…
Artem
  • 221
  • 1
  • 3
10
votes
1 answer

Why is my GAN more unstable with bigger networks?

I am working with generative adversarial networks (GANs) and one of my aims at the moment is to reproduce samples in two dimensions that are distributed according to a circle (see animation). When using a GAN with small networks (3 layers with 50…
Mafu
  • 144
  • 5
7
votes
3 answers

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

I'm making a Connect Four game where my engine uses Minimax with Alpha-Beta pruning to search. Since Alpha-Beta pruning is much more effective when it looks at the best moves first (since then it can prune branches of poor moves), I'm trying to come…
Inertial Ignorance
  • 511
  • 3
  • 14
7
votes
4 answers

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

I read about minimax, then alpha-beta pruning, and then about iterative deepening. Iterative deepening coupled with alpha-beta pruning proves to quite efficient as compared to alpha-beta alone. I have implemented a game agent that uses iterative…
Suhail Gupta
  • 171
  • 1
  • 5
7
votes
1 answer

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), then $h$ is called monotone, or consistent. In…
Shrey Shrivastava
  • 71
  • 2
6
votes
2 answers

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: h(B)=9 h(D)=10 h(A)=2 h(C)=1 If we use the A* algorithm, the node $B$ will…
hellojoshhhy
  • 163
  • 1
  • 3
6
votes
1 answer

Can two admissable heuristics not dominate each other?

I am working on a project for my artificial intelligence class. I was wondering if I have 2 admissible heuristics, A and B, is it possible that A does not dominate B and B does not dominate A? I am wondering this because I had to prove if each…
JRowan
  • 163
  • 5
4
votes
3 answers

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

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 heuristic do we have to use when we have multiple…
dragan
  • 41
  • 1
  • 2
4
votes
1 answer

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

I am interested in the current state-of-the-art ways to use quick, greedy heuristics in order to speed up the learning in a Deep Q-Network in Reinforcement Learning. In classical RL, I initially set the Q-value for a state-action pair (S,a) based on…
AlexGuevara
  • 273
  • 2
  • 8
4
votes
1 answer

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

Let's suppose I have a set of heuristics $H$ = {$h_1, h_2, ..., h_N$}. If all heuristics in $H$ are admissible, does that mean that a heuristic that takes the $\min(H)$ (or $\max(H)$ for that matter) is also admissible? If all heuristics in $H$ are…
ihavenoidea
  • 265
  • 2
  • 11
4
votes
1 answer

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

I was given the following problem to solve. Given a circular trail divided by $n> 2$ segments labeled $0 \dots n-1$. In the beginning, an agent is at the start of segment number $0$ (the edge between segments $n-1$ and $0$) and the agent's speed…
hpr16
  • 41
  • 2
3
votes
0 answers

Snake path finding variant : Algorithm choice

I am working on a project which maps to a variant of path finding problem. I am new to this area and I would be very grateful if you could give suggestions/ point to libraries for relevant algorithms. A simplified version of my problem statement is…
Pranav M
  • 31
  • 3
3
votes
3 answers

Does a consistent heuristic have value 0 on a goal state?

I was studying AI when a question came to my mind. In the context of search problems, a heuristics is a non-negative real-valued function on the space of states. A heuristic is said to be consistent if it satisfies the triangle-equality-like…
Amanda Wealth
  • 183
  • 6
1
2 3 4