Admissible Heuristic and Hill Climbing Search

Part 1: Admissible Heuristic (3 marks)

Definition

An admissible heuristic is a heuristic function h(n) that never overestimates the true cost of reaching the goal from node n. In other words, for every node n:

h(n) <= h(n)*

where h*(n) is the actual (true) cost from node n to the goal.

An admissible heuristic is always optimistic - it either correctly estimates or underestimates the remaining cost. This property is crucial because it guarantees that search algorithms like A* will find the optimal (least-cost) solution.

Formal Condition

For a heuristic h(n) to be admissible:

• h(n) >= 0 for all nodes n
• h(goal) = 0
• h(n) <= h*(n) for all nodes n

Example

Consider finding the shortest path on a map (Romania problem):

• h(n) = straight-line distance (Euclidean distance) from node n to the goal city.

Since the straight-line distance between two points is always less than or equal to the actual road distance, this heuristic never overestimates the true cost. Therefore, it is admissible.

Here h(A) = 366 <= 418 = h*(A), so the condition holds.

Another simple example: In the 8-puzzle problem, the number of misplaced tiles is an admissible heuristic because each misplaced tile requires at least one move to reach its goal position, so it never overestimates.

Part 2: Hill Climbing Search (7 marks)

Definition

Hill Climbing is a heuristically informed local search technique that continuously moves in the direction of increasing value (or decreasing cost) to find the best solution. It belongs to the category of heuristically informed search methods that use domain-dependent information to search more efficiently.

The algorithm works like climbing a hill - at each step, you move to the neighbor that is "higher" (better) than the current position, until no higher neighbor exists.

Working Mechanism

The algorithm uses an evaluation function h(n) (heuristic) to measure the quality of each state. The state with the lowest heuristic value (closest to goal) is selected next.

Algorithm Steps:

1. Start with an initial state (current node).
2. Evaluate the current state using heuristic h(n).
3. Generate all successors (neighbors) of the current state.
4. Evaluate each successor using h(n).
5. Select the successor with the best (lowest h(n)) value.
6. If the best successor is better than the current state:
      - Move to that successor (current = best successor)
      - Go to Step 3.
7. If no successor is better than the current state:
      - STOP. Current state is the local maximum/minimum.

Illustrated Example:

Consider nodes with heuristic values (h = estimated distance to goal):

Start: S (h=12)
       |
   ---------
   |       |
   B(h=4)  D(h=5)
   |
   E(h=7)  G1(h=0) <-- Goal

Step 1: At S, h(S) = 12. Successors: B(h=4), D(h=5).

• Best successor = B (h=4 < h=5). Move to B.

Step 2: At B, h(B) = 4. Successors: E(h=7), G1(h=0).

• Best successor = G1 (h=0). Move to G1.

Step 3: G1 is the goal. Search complete.

Path: S --> B --> G1

Types of Hill Climbing

Limitations of Hill Climbing

Hill climbing suffers from three major problems:

1. Local Maxima (Local Optima)

• The algorithm may reach a state that is better than all its neighbors but is not the global optimum.
• Once at a local maximum, the algorithm stops even though a better solution exists elsewhere.

Global Max
     /\
    /  \
   / LM \      <-- Algorithm gets stuck at Local Max (LM)
  /  /\  \
 /  /  \  \
Start

2. Plateaus (Flat Local Maxima)

• A plateau is a flat area in the search space where all neighboring states have the same evaluation value.
• The algorithm cannot determine which direction to move, so it may wander randomly or stop.
• This makes progress very slow or impossible.

h(n) = 5 --- 5 --- 5 --- 5   <-- Plateau (no uphill direction)

3. Ridges

• A ridge is a sequence of local maxima that is difficult for the algorithm to navigate.
• The path to the global optimum may require moving sideways or downhill temporarily, but hill climbing never does this.
• The algorithm gets stuck because no single step leads uphill toward the true goal.

      Ridge
     /     \
    /  Goal  \
---/-----/----\---
  /     /      \

Summary Table of Limitations

Overcoming the Limitations

Simulated annealing carries the same idea further by occasionally accepting a worse state, with a probability that falls as the search proceeds, so the search can escape a local maximum early on and still settle on a good solution later.

Conclusion

Hill climbing is attractive because it stores only the current state, needs very little memory and often reaches a good solution quickly. It is, however, neither complete nor optimal: it accepts the best immediate move and never looks beyond its own neighbourhood, so it can terminate at a local maximum, on a plateau or against a ridge. When the optimal solution is required, an admissible heuristic is used with a systematic search such as A*, which the admissibility condition h(n) <= h*(n) guarantees will return the least cost path. Hill climbing is preferred when a reasonably good solution has to be found quickly in a state space too large to search systematically.

Expert System: Definition, Example, and Stages of Development

1. Definition of Expert System

An Expert System is a computer program that simulates the judgment and behavior of a human expert or an organization that has expert knowledge and experience in a particular field. It is a knowledge-based system that uses a collection of knowledge (stored in a knowledge base) and an inference engine to solve complex problems that normally require human expertise.

An expert system captures the knowledge of human specialists and makes it available to non-experts for decision making, diagnosis, or problem solving in a specific domain.

Key Components of an Expert System

Example

Medical Diagnosis Expert System (MYCIN): MYCIN was one of the earliest expert systems developed at Stanford University. It was designed to diagnose bacterial infections and recommend antibiotics. A doctor could input patient symptoms and test results, and MYCIN would provide a diagnosis along with recommended treatment, mimicking the reasoning of a medical expert.

Other examples include:

• R1/XCON - Used by Digital Equipment Corporation (DEC) for computer configuration (first successful commercial expert system, 1982)
• DENDRAL - Used for chemical analysis
• Tax advisory systems - Used in financial planning

2. Stages of Expert System Development

: "An expert system typically is developed and refined over a period of several years."

The following are the major stages of expert system development:

Stage 1: Problem Identification and Feasibility Study

• The problem domain is identified and analyzed.
• Experts and knowledge engineers determine whether the problem is suitable for an expert system solution.
• Questions addressed:
  • Is the problem well-defined?
  • Is there a genuine need for an expert system?
  • Is the required expertise available?
• A feasibility study is conducted to check technical, economic, and operational viability.

Stage 2: Knowledge Acquisition

• This is the most critical and time-consuming stage.
• Knowledge is gathered from human domain experts, books, databases, case studies, and documents.
• The knowledge engineer (developer) interviews experts and extracts:
  • Facts about the domain
  • Rules and heuristics used by experts
  • Decision-making strategies
• Challenges: Experts may find it difficult to articulate their implicit knowledge.

Stage 3: Knowledge Representation

• The acquired knowledge is organized and represented in a form that the computer can process.
• Common representation techniques:
  • Production Rules (IF-THEN rules)
  • Semantic Networks
  • Frames
  • Predicate Logic
• Example of a production rule:

  IF  patient has fever AND cough
  THEN  suspect respiratory infection
  

Stage 4: Prototype Development

• A small-scale prototype of the expert system is built using the represented knowledge.
• This prototype is tested with simple cases to verify the basic structure and logic.
• Tools used: Expert System Shells (e.g., CLIPS, JESS, Prolog)
• The prototype helps identify gaps in knowledge and design flaws early.

Stage 5: Testing and Validation

• The prototype is tested with real-world cases and compared against decisions made by actual human experts.
• Validation ensures the system produces correct and reliable outputs.
• Verification ensures the system is built correctly according to specifications.
• Errors in rules or knowledge are identified and corrected.

Stage 6: Refinement and Expansion

• Based on testing feedback, the knowledge base is refined and expanded.
• New rules are added, incorrect rules are modified or removed.
• The system is gradually scaled up from a prototype to a full system.
• This stage may repeat multiple times (iterative process).

Stage 7: Integration and Deployment

• The fully developed expert system is integrated into the working environment.
• It is deployed for actual use by end users (non-experts).
• User training and documentation are provided.
• The system is connected to existing databases and organizational systems if needed.

Stage 8: Maintenance and Knowledge Update

• The expert system is maintained over time.
• The knowledge base is updated periodically as new knowledge becomes available or the domain changes.
• Performance is monitored and improvements are made continuously. -: "It updates knowledge periodically if agent is able to acquire new knowledge."

Summary Diagram of Stages

Problem Identification
        |
        v
Knowledge Acquisition
        |
        v
Knowledge Representation
        |
        v
Prototype Development
        |
        v
Testing and Validation
        |
        v
Refinement and Expansion
        |
        v
Integration and Deployment
        |
        v
Maintenance and Update

Conclusion

Expert systems represent a significant milestone in Artificial Intelligence, as demonstrated by the success of systems like R1 at Digital Equipment Corporation which saved millions of dollars per year. The development of an expert system is an iterative, multi-stage process that requires close collaboration between knowledge engineers and domain experts to build a reliable, accurate, and maintainable system.