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.
49 questions
0
votes
0
answers
54
views
Train AI to schedule a league with certain constraints
I need some suggestions on options to look into to train an AI model to schedule sporting events based on certain constraints. Contraints like no back to back games, 2 games per day, 1 per week, keep ...
- 101
0
votes
0
answers
116
views
Minimum remaining values heuristic more powerful than degree heuristic
When selecting a new variable to assign a value to in CSP assignment backtracking search, common heuristics include:
MRV heuristic: pick the unassigned variable with the fewest remaining values in ...
- 101
0
votes
1
answer
110
views
How do we know that $c(n,a,G) = h^{\ast}(n)$, in the proof that if a heuristic is consistent then it is admissible?
I found a proof that if a heuristic $h$ is consistent, then it is admissible, but I'm confused by one of the steps in the proof.
The proof is by induction on $k$, the number of actions from a node $n$ ...
2
votes
1
answer
394
views
How to determine that an heuristic is admissible
An heuristic is admissible if never overestimates the real cost to reach the goal.
In order to prove that an heuristic $h$ is admissible we need to prove that for every state $s$ in the state space we ...
- 21
0
votes
0
answers
141
views
What is a good algorithm (and a heuristic) to find the shortest path in a puzzle game?
In a 3D world, there is a Robot, boxes, and switches. The robot's job is to carry boxes (one box at a time) and put them on top of switches to solve the level. All switches must have a box on top for ...
- 1
0
votes
0
answers
71
views
What is the theory behind rejecting too good heuristics in search problems?
Currently I have found that there is an article in which a search problem is posed and to solve it a heuristic is proposed which, in essence, is the solution of the problem itself. I seem to remember ...
- 211
0
votes
1
answer
458
views
how to apply crossover and mutation rates in genetic algorithm?
I'm working with genetic programming and let's say I have the following operator:
pop_size = 100
Crossover ratio = 0.4
Mutation Ratio = 0.2
Selection Ratio = 0.1
What is exactly the next generation ...
- 1
0
votes
0
answers
806
views
Why is the greedy heuristic admissible and consistent for food at corners problem, but not for food anywhere problem?
UCBerkley has a great Intro to AI course (CS188) where you can practice coding up search algorithms. One of the exercises (question 6), asks to generate a heuristic that will have Pacman find all 4 ...
- 143
1
vote
0
answers
137
views
Is N the total number of nodes in the frontier plus the number of nodes in the explored list?
I'm studying fundamentals of AI from the classic Russell-Norvig book (3rd edition). I have a small doubt about the effective branching factor, which is defined as follows (section 3.6.1, p. 103):
One ...
- 111
0
votes
0
answers
327
views
Is possible to perform an early goal test with A* using a consistent heuristic?
I have a doubt about A* goal test.
As far as I know an early goal test is performed when a node (representing a certain state) is inserted in the frontier or, to conform with AIMA terminology, when is ...
- 21
1
vote
1
answer
351
views
Can Deep Reinforcement Learning come up with heuristics for a game it trains on and masters?
I am taking a course where we write minimax, alpha-beta pruning and interative deepening in Python for the game of Isolation.
I am supposed to write heuristics for an evaluation function of the game ...
- 115
3
votes
0
answers
592
views
Are there heuristics that play Klondike Solitaire well?
Are there heuristics that play Klondike Solitaire well?
I know there are some good exhaustive search solvers for Klondike Solitaire. The best one that I know of is Solvitaire (2019) which uses DFS, (...
- 413
1
vote
1
answer
2k
views
Determining minimal state representation for maze game
I came across this question set. It asks following question:
Let’s revisit our bug friends from assignment 2. To recap, you control one or more insects in a rectangular maze-like environment with ...
- 151
-1
votes
0
answers
59
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 ...
- 19
10
votes
1
answer
882
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 ...
- 144
1
vote
0
answers
34
views
CSP heuristic to simultaneously reduce conflicts and find near optimal assignment
I am trying to design a good heuristic to solve a constraint satisfaction problem (CSP). I think that a possible heuristic to use is
$$h_1(\text{state}) = \text{number of conflicts in state}$$
However,...
- 11
2
votes
1
answer
126
views
How can I improve the performance of my approach to solving a 1-player version of the card game "The Game" by Steffen Benndorf?
I would like to create an AI for the 1 player version of the card game called "The Game" by Steffen Benndorf (rules here: https://nsv.de/wp-content/uploads/2018/05/the-game-english.pdf).
The ...
- 123
3
votes
1
answer
3k
views
Is A* with an admissible but inconsistent heuristic optimal?
I understand that, in tree search, an admissible heuristic implies that $A*$ is optimal. The intuitive way I think about this is as follows:
Let $P$ and $Q$ be two costs from any respective nodes $p$ ...
- 161
1
vote
1
answer
2k
views
Which heuristics guarantee the optimality of A*?
The following is a statement and I am trying to figure out if it's true or false and why.
Given a non-admissible heuristic function, A* will always give a solution if one exists, but there is no ...
- 25
2
votes
1
answer
226
views
Why aren’t heuristics for Connect Four Monte Carlo tree search improving the agent?
I’ve created an agent using MCTS to play Connect Four. It wins against humans pretty well, but I’d like to improve upon it. I decided to add domain knowledge to the MCTS rollout stage. My evaluation ...
- 633
2
votes
0
answers
158
views
How does heuristic work with multiple agents?
I have a question for heuristic search with multiple agents. I know how heuristic search works with one agent (ex. one Pacman) but I don't really understand it with multiple agents. Let's say we have ...
- 121
2
votes
1
answer
119
views
Agents meeting in a directed connected graph
We have a directed connected graph, where nodes are places one can go to and edges are the "roads" between places. We have K agents whose goal is to meet in one node. Agents start in ...
- 161
3
votes
1
answer
2k
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 ...
- 177
3
votes
0
answers
1k
views
Can the degree and minimum remaining values heuristics be used in conjunction?
I am currently studying constraint satisfaction problems and have come across two heuristics for variable selection. The minimum remaining values(MRV) heuristic and the degree heuristic.
The MRV ...
- 1,291
2
votes
1
answer
93
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 ...
- 2,246
3
votes
0
answers
359
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 ...
6
votes
1
answer
1k
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 ...
- 163
2
votes
1
answer
4k
views
Understanding the proof that A* search is optimal
I don't understand the proof that $A^*$ is optimal.
The proof is by contradiction:
Assume $A^*$ returns $p$ but there exists a $p'$ that is cheaper. When $p$ is chosen from the frontier, assume $...
- 351
7
votes
1
answer
396
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),...
4
votes
1
answer
5k
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) ...
- 265
4
votes
1
answer
1k
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 ...
- 41
2
votes
3
answers
723
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 ...
- 187
2
votes
0
answers
64
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 ...
- 143
4
votes
3
answers
9k
views
What heuristic to use when doing A* search with multiple targets? [closed]
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 ...
- 41
7
votes
3
answers
1k
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 ...
0
votes
1
answer
11k
views
How do you calculate the heuristic value in this specific case?
The A* algorithm uses the "evaluation function" $f(n) = g(n) + h(n)$, where
$g(n)$ = cost of the path from the start node to node $n$
$h(n)$ = estimated cost of the cheapest path from $n$ to the ...
- 371
13
votes
1
answer
31k
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 ...
- 303
3
votes
0
answers
442
views
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. ...
- 31
1
vote
0
answers
29
views
Approach for data transformation needed
I am looking for an algorithm to transform an input data to a goal data using a series of operations. The shorter the series the better.
The following is known:
the input data
the goal data
input ...
- 111
7
votes
4
answers
6k
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 ...
- 171
2
votes
0
answers
55
views
How to open up a rigid structure made of connected panels?
By open up I mean slightly open up so that a theoretical structure of panels with no width looks three-dimensional. The original structure being an ideal object where any number several panels can ...
- 121
12
votes
1
answer
214
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 ...
- 221
-1
votes
0
answers
806
views
Has Tic-Tac-Toe been solved with a single heuristic?
By this I mean a single axiom for placement. (I'm working on a solution that involves positional valuation and vectors, and appears to be solid, but my assumption would be this has been done ...
- 6,233
4
votes
1
answer
90
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 ...
- 273
6
votes
2
answers
3k
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:
...
- 163
2
votes
0
answers
58
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 ...
- 29
3
votes
1
answer
116
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 ...
- 91
2
votes
3
answers
81
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:
...
- 464
12
votes
5
answers
1k
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 ...
- 2,523