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.

Filter by
Sorted by
Tagged with
0 votes
1 answer
84 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$ ...
1 vote
0 answers
57 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 ...
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 ...
2 votes
1 answer
104 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 ...
10 votes
1 answer
538 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 ...
0 votes
0 answers
109 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 ...
0 votes
0 answers
49 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 ...
0 votes
1 answer
336 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 ...
0 votes
0 answers
572 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 ...
2 votes
1 answer
111 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 ...
1 vote
0 answers
123 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 ...
0 votes
0 answers
251 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 ...
2 votes
1 answer
3k 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 $...
1 vote
1 answer
260 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 ...
2 votes
1 answer
121 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 ...
13 votes
1 answer
29k 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 ...
3 votes
0 answers
487 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, (...
2 votes
1 answer
164 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 ...
0 votes
0 answers
44 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 ...
6 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 ...
1 vote
0 answers
31 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,...
7 votes
1 answer
366 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),...
3 votes
3 answers
8k 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 ...
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$ ...
1 vote
1 answer
1k 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 ...
0 votes
1 answer
10k 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 ...
2 votes
3 answers
714 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 ...
2 votes
0 answers
131 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 ...
3 votes
1 answer
113 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 ...
3 votes
1 answer
1k 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 ...
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 ...
2 votes
1 answer
80 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 ...
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 ...
4 votes
1 answer
4k 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) ...
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 ...
6 votes
2 answers
2k 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: ...
3 votes
1 answer
987 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 ...
3 votes
0 answers
336 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 ...
12 votes
1 answer
206 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 ...
2 votes
0 answers
63 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 ...
11 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 votes
0 answers
423 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. ...
1 vote
0 answers
27 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 ...
2 votes
0 answers
51 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 ...
0 votes
0 answers
800 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 ...
4 votes
1 answer
84 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 ...
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: ...