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
2
votes
1answer
23 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 ...
1
vote
1answer
32 views

Why is the effective branching factor used for measuring performance of a heuristic function?

For search algorithms with heuristic functions, performance of heuristic functions are measured by effective branching factor ${b^*}$ which involves total nodes expanded ${N}$ and depth of the ...
4
votes
2answers
128 views

If an heuristic is not admissible, can it be consistent?

I am solving a problem in which, according to the given values, the heuristic is not admissible. According to my calculation from other similar problems, it should be consistent, as well as keeping in ...
3
votes
0answers
30 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
1answer
54 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 ...
5
votes
1answer
86 views

How do we determine whether a heuristic is better than another?

I am trying to solve a Maze puzzle using the A* algorithm. I am trying to analyze the algorithm based on different applicable heuristics. Currently, I explored the Manhattan and Euclidean distances. ...
0
votes
0answers
18 views

Tweaking MCTS to account for opponent knowing the state of the game

I'm making an artificial intelligence for a card game using MCTS. With a standard 52-cards deck, 4 hands are dealt: 1 for each of the 3 players and one extra hand. Then, each player gets the choice to ...
2
votes
1answer
68 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 $...
2
votes
1answer
85 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) ...
3
votes
1answer
151 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 ...
2
votes
1answer
153 views

Why Nilsson's Sequence Score isn't an admissible heuristic?

I understand what an admissible heuristic is, I just don't know how to tell whether one heuristic is admissible or not. So, in this case, I'd like to know why Nilsson heuristic isn't admissible.
2
votes
3answers
309 views

Heuristic function for BayesChess

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 ...
4
votes
1answer
43 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 ...
2
votes
3answers
2k views

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

The problem of multi-goal path planning was introduced in an ICRA paper in the year 2011: “Multi-goal planning is a task which arises in many robotics applications. It combines the challenging ...
6
votes
3answers
414 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
1answer
1k 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 ...
4
votes
1answer
148 views

Why has the General problem solver failed?

I'm reading currently through the old papers of Allen Newell and Herbert Simon in the late 1950s about their project to build a general problem solver. As far as i understand the concept of operators ...
7
votes
1answer
6k 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
1answer
218 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
0answers
17 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
0answers
45 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 ...
3
votes
1answer
554 views

How do I write a good evaluation function?

I'm currently writing an Alpha-Beta-Pruning algorithm for a board game. Now I need to come up with a good evaluation function. The game is a bit like snakes and ladders (you have to finish the race ...
2
votes
2answers
450 views

Evaluation Function for a Go like game

I am trying to find a good evaluation function for a game with: A 7x7 tile board 2 players, given equal number(>=3 currently undetermined) of stones placed randomly on the tiles A turn is consisted ...
11
votes
1answer
160 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 ...
3
votes
1answer
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 ...
1
vote
0answers
723 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
1answer
61 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 ...
5
votes
1answer
109 views

Reproduce Firefly Algorithm experiments of original paper?

I have been trying to reproduce the experiments done in the original: "Firefly Algorithm for multimodal optimization" (linked in the question) so far: unsuccessfully. For the moment being I'm okay if ...
5
votes
2answers
186 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: ...
2
votes
0answers
35 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 ...
3
votes
3answers
62 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: ...
12
votes
6answers
473 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 ...