# 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.

42 questions
Filter by
Sorted by
Tagged with
14k views

### 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 ...
889 views

### 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 ...
188 views

### 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 ...
664 views

### 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 ...
166 views

### 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),...
83 views

### 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 ...
876 views

### 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: ...
4k views

### 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 ...
158 views

### 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 ...
2k views

### Blocks world Game: A* heuristic solution approach

I am developing a heuristic solution for blocks world problem. I tried using number of blocks out of place as my h(n). It seems little ineffective. Can someone please point out a suitable heuristic ...
70 views

### 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 ...
363 views

### Is the summation of consistent heuristic functions also consistent?

Imagine that we have a set of heuristic functions $\{h_i\}_{i=1}^N$, where each $h_i$ is both admissible and consistent (monotonic). Is $\sum_{i=1}^N h_i$ still consistent or not? Is there any proof ...
76 views

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

This is a question about a nomenclature - we already have the algorithm/solution, but we're not sure whether it qualifies as utilizing heuristics or not. feel free to skip the problem explanation: ...
1k views

### 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) ...
329 views

### 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 ...
94 views

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

Is there any methodology to find proper parameter settings for a given meta-heuristic algorithm, e.g. the firefly algorithm or the cuckoo search? Is this an open issue in optimization? Is extensive ...
120 views

### How to choose the weights for a linear combination of heuristic functions?

I need to write a minimax algorithm with alpha-beta pruning in limited time for the 2048 game. I know expectimax is better for this work. Assume I wrote different heuristic functions. If I want to ...
54 views

### What kind of decision rule algorithm is usable in this situation?

I am trying to write an AI to a game, where there is no real adversary. This means, that only the AI player has choices in which move to perform, his opponent may or may not react to the move the AI ...
38 views

### Knapsack of mixture with constraints

I'm trying to find the optimized mixture for a specific set of substances. Each of those substances have characteristics that I want to optimize in the mixture (some characteristics I want to minimize ...
633 views

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

I am reading BayesChess: A computer chess program based on Bayesian networks (Fernandez, Salmeron; 2008) It is a chess-playing engine using Bayesian networks. The following is mentioned about the ...
50 views

### What are some common heuristics that might be innate?

Here's a question I might ask an AI to solve: "Colour the states of the USA using just 4 colours". Now, a common heuristic a human might use is to start at one ...
404 views

15 views

### Why is that the heuristic is not admissible, then it is not consistent [duplicate]

I don't understand why if the heuristic is not admissible then it is not consistent?
29 views

### Incorrect node expansion in game board with A* search

I have the following game board below, and we're using A* search to find the optimal path from the agent to the key. There are 8 directions. Up, down, left, right have a cost of 1, and diagonal ...
24 views

### Can an inadmissable heuristic be consistent? [duplicate]

If something is inadmissible, can we just assume it's also inconsistent? Also, I understand how to check if a heuristic is inadmissible, but I'm still a bit confused on checking consistency. If I have ...
23 views

### Satisficing searches - how does speedy search compensate for higher execution costs

While reading AI: A Modern Approach (4th ed), I have some difficulty in coming to terms with the usefulness of a satisficing search. Generally speaking, I understand that in real life situations we ...