# 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
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?
46 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, (...
58 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 ...
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 ...
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 ...
19 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,...
354 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$ ...
139 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 ...
71 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 ...
41 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 ...
52 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 ...
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 ...
286 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 ...
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 ...
646 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 ...
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 ...
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 ...
404 views

292 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. ...
21 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 ...
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 ...
48 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 ...
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 ...
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 ...
761 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 ...
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 ...
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: ...
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 ...
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 ...