Yugensys | Outsourced Product Development

Heuristic functions are essential tools in artificial intelligence (AI) and cognitive psychology, designed to simplify complex decision-making processes by focusing on key factors. These functions serve as mental shortcuts or rules of thumb, enabling quick judgments without the need to evaluate all possible information. Heuristics are particularly useful when time, resources, or cognitive capacities are limited. They help us navigate complex environments efficiently, but their effectiveness depends on choosing the right heuristic. An appropriate heuristic can lead to good decisions swiftly, while an ill-chosen one might result in poor outcomes.

What is Heuristic function?

When performing an informed search, we use this as a tool to make decisions between alternatives without needing all the information about each option.

When we use a heuristic function, we base our decision on one key feature or characteristic that we believe differentiates the options. Instead of considering all possible reasons to choose one alternative over another, we pick one reason and make our decision solely based on that.

Heuristic functions are commonly used in search algorithms to make the search process more efficient by estimating the cost or distance to the goal. Here are some well-known search algorithms that utilize heuristic functions:

Greedy Best-First Search:

Heuristic Function: h(n)
Cost Function: g(n) (actual cost from the start node)

Description: Combines the actual cost to reach the node𝑔(𝑛)
g(n) and the heuristic estimateℎ(𝑛)
h(n) to guide the search.

The function f(n)=g(n)+h(n) determines the order of node expansion. It is complete and optimal ifℎ(𝑛)
h(n) is admissible (never overestimates the true cost).

IDA (Iterative Deepening A*:

Heuristic Function: ℎ(𝑛)
Description: An iterative deepening variant of A* Search. It performs a series of depth-limited searches using increasing bounds on𝑓(𝑛). It combines the benefits of depth-first search and A*.

Uniform Cost Search:
Heuristic Function: ℎ(𝑛)=0

Description: A special case of A* where the heuristic function is zero. It expands nodes based on the lowest cost𝑔(𝑛)g(n) from the start node.

Simulated Annealing:

Heuristic Function: Used indirectly in guiding the search towards the goal by evaluating the quality of solutions.

Description: A probabilistic technique that explores the search space by accepting not only improvements but also some worse solutions to escape local optima. Heuristics can guide the evaluation of solutions.

Genetic Algorithm:

Heuristic Function: Used in fitness functions to evaluate the quality of solutions.

Description: Evolutionary algorithms that use heuristics to guide the evolution of solutions. Fitness functions often incorporate heuristic elements to assess and select the best candidates.

Each of these algorithms leverages heuristic functions in different ways to improve search efficiency and effectiveness.

Where This Bias Occurs

IMPROVE YOUR DECISION-MAKING

Most of us operate in environments that aren’t optimized for sound decision-making. We work with various organizations to identify sources of cognitive bias and develop tailored solutions.

LEARN ABOUT OUR WORK

Imagine you are a teacher selecting students for a special project. There are many variables to consider: academic performance, creativity, teamwork, and behavior. Faced with so many options, you might rely on one standout feature, such as academic performance, to make your choice quickly.

In situations like these, you are likely using a straightforward decision-making strategy. It would take too much time to carefully consider all the different reasons why you might choose one student over another. Factors can include their participation, previous work, punctuality, etc. So, you might pick just one reason, like academic performance, and compare the students based on that reason alone. This makes it easy for you to pick – you’ll just select the student with the highest grades!

This strategy can be applied whenever you must choose between alternatives. It simplifies decision-making but also means you’re ignoring many variables that could matter in determining the best choice.

Personal Impacts

The example of choosing students for a project makes the decision-making strategy seem rather practical and efficient. It would take too long to evaluate all the factors, so academic performance seems like a rational way to determine who to select.

In part, it’s true that this heuristic can be beneficial. It’s a form of bounded rationality, where we make decisions that satisfy our needs without wasting time and resources to determine the best possible decision. On the other hand, this means we’re only making decisions that are ‘good enough’ and not optimal.

Broader Impacts

On an individual basis, using the simple decisions seem harmless. However, it can quickly lead to decisions based on biases.

Picture yourself trying to buy a new laptop. There are numerous factors to consider: brand, price, specifications, design, and user reviews. How can you make a decision quickly when faced with so many alternatives?

Imagine deciding based on a single factor, say you might choose to focus solely on the brand. This means you consistently choose laptops from a brand you trust without considering other important factors like price or specifications.

Why This Happens?

We make hundreds of decisions daily. We don’t have the time, energy, or resources to consider all available information for each decision. So, our brain uses heuristic functions to make quick decisions, and with simple strategy, we rely on one reason to rationalize our choice.

When faced with alternatives, we quickly register different criteria cues and single one out. The chosen cue is usually the first one we determine adequately differentiates between options and makes our choice easy. Returning to the example of selecting a laptop, brand recognition might not be a likely candidate for a chosen cue as it is too broad. Price or specifications, alternatively, clearly differentiate between alternatives.

The steps involved in the identifying the right heuristic function for the given problem can be determined by the following factors:

Search Rule: Look through cues and evaluate which one will allow for fast but accurate decisions.
Stopping Rule: Stop the search when you encounter the first cue that will differentiate between alternatives.
Decision Rule: Make a decision based on which scores better according to the chosen cue.

Importance of Heuristic Functions

We use heuristic functions unconsciously in many daily decisions. These heuristics allow us to make good decisions even when we have constraints like time, available knowledge, and cognitive ability. In AI, heuristic functions are used to guide search algorithms, optimize solutions, and make real-time decisions. However, it’s crucial to define and select the right heuristic to ensure the decisions are both efficient and effective.

Example 1 – Elections

Close to an election, our TVs, newspapers, and even our social media sites are flooded with information about the politicians in the running. Even if we put aside that a lot of it is fake news, it’s difficult to meaningfully register the real information and analyze it to make the best decision on who to vote for. How can we predict which politician will best address the issues we care about?

Choosing what we believe to be the most important issue facing the country and deciding which politician we think will best address it, is one way to surpass the information overload and make an informed vote. In 2012, business student J. Scott Armstrong and systems analysis student Andreas Graefe conducted a study that inferred whether a simple heuristic is used when voting.

The study looked at elections retrospectively. They realized that many people do not properly know how the government works but somehow, end up ‘correctly’ voting. By correctly, Armstrong and Graefe meant that even without all knowledge, people tend to make decisions they would have chosen if they had all the information available. They analyzed data on which issue voters regarded as being the most important issue facing the country for 100 days before the election and which candidate people thought would best address that issue. They found the candidate that was thought to best address the major issue almost always won the popular vote, which suggested that was the criterion individuals were using to make their decision.

From their study, Armstrong and Graefe concluded that politicians should focus on developing their campaign for the most important issue faced by the country, rather than try and tackle all the different problems, as people have a tendency to decide depending on what affects them the most when voting.

Example 2 – Risk Assessment in Security

Imagine an airport security officer using a simple heuristic when determining who to select for a random search. There are so many variables that could determine which passengers they select – their age, how many people they are traveling with, how much luggage they have, or, more problematically, their race. The airport security officer may make discriminatory decisions, singling out a particular race as being more dangerous and requiring a random search.

How to Avoid Misusing Heuristics

Heuristic functions simplify and speed up our decision-making process, often leading to more accurate outcomes than if we tried to process all available information. The key is not to avoid heuristics but to ensure that the cues guiding our decisions are valid and relevant.

1. Heuristic Function Definitions and Formulas

A heuristic function, often denoted as \(h(x)\), is used to rank alternatives based on available information. In artificial intelligence (AI), heuristic functions estimate the cost or value associated with a particular option, helping to select the alternative with the best estimated outcome.

For instance, in the context of search algorithms, a heuristic function \(h(n)\) estimates the cost to reach the goal from node \(n\).

2. Sample Derivation Using Heuristic Formula

Consider the example of a heuristic function used in pathfinding algorithms. Let’s define h(n) as the straight-line distance (Euclidean distance) from node n to the goal node G.

If node n is at coordinates (\(x_n, y_n\)) and the goal G is at coordinates (\(x_G, y_G\)), the heuristic function \(h(n)\) can be defined as:

\[h(n) = \sqrt{(x_G – x_n)^2 + (y_G – y_n)^2}\]

3. Example Calculation

Suppose a node is located at coordinates (3, 4) and the goal is at coordinates (7, 1). The heuristic function \(h(n)\) would be calculated as:

\[h(n) = \sqrt{(7 – 3)^2 + (1 – 4)^2} = \sqrt{4^2 + (-3)^2} = \sqrt{16 + 9} = \sqrt{25} = 5\]

This value indicates that the estimated cost to reach the goal from the node (3, 4) is 5.

4. Applying Heuristic Functions in AI Algorithms

Heuristic functions are essential in guiding AI algorithms, particularly in search and optimization tasks. They help navigate complex decision spaces by providing estimates that make the search process more efficient. Let’s explore their usage in two popular search algorithms: Greedy Best-First Search and A* Search.

• Greedy Best-First Search

Greedy Best-First Search uses a heuristic function to select the node that appears to be closest to the goal. The algorithm prioritizes nodes with the lowest heuristic value \(h(n)\).

Initialize: Start with the initial node.
Expand: Select the node with the lowest \(h(n)\).
Goal Test: If the selected node is the goal, terminate.
Expand Neighbours: Expand the selected node’s neighbours and repeat.
While efficient, Greedy Best-First Search can get trapped in local optima since it only considers the heuristic value \(h(n)\) and not the actual cost from the start node.

• A* Search

A* Search improves upon Greedy Best-First Search by considering both the actual cost from the start node and the heuristic estimate to the goal. The function \(f(n)=g(n)+h(n)\) guides the search, where:

\(g(n)\) is the actual cost to reach node n from the start.
\(h(n)\) is the heuristic estimate from node n to the goal.

Initialize: Start with the initial node.
Expand: Select the node with the lowest \(f(n)\).
Goal Test: If the selected node is the goal, terminate.
Expand Neighbours: Expand the selected node’s neighbours and update their costs.

A* Search is both complete and optimal, provided the heuristic function h(n) is admissible (never overestimates the actual cost).

Conclusion

Heuristic functions are indispensable in AI for making efficient and effective decisions. By appropriately defining heuristic functions, we can optimize search algorithms like Greedy Best-First Search and A* Search, ensuring quick and accurate navigation through complex decision spaces. Understanding and implementing the right heuristic function \(h(x)\) is crucial in AI to balance between exploration and exploitation, ultimately enhancing the performance of AI systems.

AI, Algorithms, Computer Science, Decision Making, Intelligent Systems, Machine Learning, Search Algorithms
August 16, 2024

Vaishakhi Panchmatia

As Tech Co-Founder at Yugensys, I’m passionate about fostering innovation and propelling technological progress. By harnessing the power of cutting-edge solutions, I lead our team in delivering transformative IT services and Outsourced Product Development. My expertise lies in leveraging technology to empower businesses and ensure their success within the dynamic digital landscape.

Looking to augment your software engineering team with a team dedicated to impactful solutions and continuous advancement, feel free to connect with me. Yugensys can be your trusted partner in navigating the ever-evolving technological landscape.