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

40 questions
Filter by
Sorted by
Tagged with
68 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$ ...
61 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 ...
41 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 ...
32 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 ...
32 views

### Agents meeting in a directed connected graph

I've just started learning AI and I have a certain problem: We have directed connected graph, where nodes are places one can go to and edges are the "roads" between places. We have K agents whose ...
129 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 ...
61 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 ...
46 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 ...
208 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 ...
1k 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 ...
67 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 ...
83 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 ...
170 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. ...
131 views

260 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. ...
18 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 ...
47 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 ...
803 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 ...
746 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 ...
181 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 ...
754 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 ...
67 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 ...
117 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 ...
327 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: ...
36 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 ...
91 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 ...