Artificial Intelligence: Search, Knowledge Representation and Expert Systems
Summary
This document covers the core topics of artificial intelligence: search techniques such as blind, heuristic and game-playing methods, and how knowledge is represented through logic, networks, frames and production rules. It also explains expert systems, their architecture, development stages, tools and common difficulties.
Key points
- AI aims to perform human-like intelligence such as learning, reasoning, problem-solving and decision-making.
- BFS uses a FIFO queue and is complete but memory-intensive; DFS uses a LIFO stack, needs less memory and may get stuck.
- A* uses f(n) = g(n) + h(n), combining actual cost and estimated cost to the goal.
- Minimax selects the optimal move in a game tree, and alpha-beta pruning removes unnecessary branches when α ≥ β.
- Forward chaining reasons from facts to a conclusion, while backward chaining reasons from a goal to supporting facts.
- An expert system's architecture includes a knowledge base, inference engine, working memory, user interface, explanation facility and knowledge acquisition module.
AI refers to machines performing human-like intelligence, such as learning, reasoning, problem-solving and decision-making.
AI Languages
- LISP: symbolic processing
- PROLOG: logic programming
- Python: AI libraries
- Java/C++: AI applications
Blind Search
- BFS: FIFO queue, level-wise search, complete, memory-intensive
- DFS: LIFO stack, depth-wise search, less memory, may get stuck
Heuristic Search
Heuristic search uses h(n) to estimate the distance to the goal.
- Hill Climbing: chooses the best neighbour. Problems include local maxima, plateaus and ridges.
- Best-First Search: expands the most promising node.
- A*: f(n) = g(n) + h(n), combining actual cost and estimated cost.
- AO*: searches AND-OR graphs; AND requires all branches, while OR selects one.
Game Playing
A game tree has MAX and MIN levels. Minimax selects the optimal move. Alpha-Beta Pruning removes unnecessary branches and prunes when α ≥ β.
Knowledge Representation (KR)
Knowledge representation stores knowledge for reasoning. Its requirements are representational adequacy, inferential adequacy, inferential efficiency and acquisitional efficiency.
- Predicate Logic: predicates, variables, constants, quantifiers ∀ (all) and ∃ (exists), and connectives AND, OR, NOT and implication.
- Logic Programming: PROLOG uses facts, rules and queries.
- Semantic Networks: nodes represent objects or concepts, links represent relationships, and inheritance is supported.
- Frames: structured knowledge using slots and values, with default values and inheritance.
- Constraint Propagation: applies constraints to reduce possible values and solve problems.
- Production Rules: IF condition THEN action/conclusion.
Inference
- Forward Chaining: from facts to conclusion (data-driven)
- Backward Chaining: from goal to supporting facts (goal-driven)
Expert Systems
An expert system is an AI program that uses expert knowledge to solve domain-specific problems.
Architecture
- Knowledge Base: stores facts and rules
- Inference Engine: applies rules
- Working Memory: stores current facts
- User Interface: handles interaction
- Explanation Facility: explains decisions
- Knowledge Acquisition Module: collects expert knowledge
Characteristics
High performance, reliability, explanation, consistency and domain expertise. Knowledge is organised as facts, rules, heuristics and relationships.
Types
Rule-based, frame-based, model-based, fuzzy, neural and hybrid systems.
Applications
Diagnosis, prediction, planning, design, monitoring, interpretation and debugging.
Advantages and Limitations
- Advantages: fast, consistent, available, preserves expertise
- Limitations: costly development, narrow domain, knowledge acquisition bottleneck, lacks human common sense
Expert System Tools and Development
Expert system tools include languages, shells and development environments. KR techniques include rules, frames, semantic networks, logic and objects.
Knowledge Engineering
Knowledge engineering involves acquiring, organising, representing and validating expert knowledge. The knowledge engineer converts expert knowledge into a usable system.
System-Building Aids and Support Facilities
- Editors, debuggers, rule managers, explanation tools and interface builders
- Knowledge acquisition, verification, validation, explanation, maintenance and user support
Development Stages
Problem identification → feasibility study → knowledge acquisition → knowledge representation → prototype → testing and validation → implementation → maintenance.
Expert System Shell
A shell is a ready-made inference engine and interface without a domain knowledge base. Examples: CLIPS, JESS and EMYCIN.
Building Process and Planning
Development involves identifying the problem, defining scope, selecting experts, acquiring knowledge, designing KR, building a prototype, testing, deploying and maintaining the system.
Tool Selection
Consider cost, compatibility, language, inference mechanism, explanation facility, ease of use, flexibility and maintenance.
Knowledge Acquisition
Methods include interviews, observation, questionnaires, case studies, documents and expert discussions.
Building Process
Problem selection → expert identification → knowledge collection → conceptualisation → formalisation → implementation → verification → validation → deployment.
Difficulties
- Experts may be unavailable
- Knowledge may be incomplete or conflicting
- Tacit knowledge is hard to express
- Rules may change
Planning Pitfalls
- Unclear goals
- Oversized scope
- Poor tool selection
- Insufficient testing
- Unrealistic budget
- Weak user involvement
Domain Expert and Success Factors
The domain expert provides specialist knowledge, and the knowledge engineer extracts and converts it into rules and representations. Success depends on a narrow scope, expert cooperation, good knowledge quality, suitable tools, continuous testing and regular updates.
Download
PDF Word HTMLFAQ
What is the difference between BFS and DFS?
BFS uses a FIFO queue and searches level by level, making it complete but memory-intensive. DFS uses a LIFO stack, searches depth-wise, needs less memory and may get stuck.
What is the difference between forward and backward chaining?
Forward chaining is data-driven and moves from facts to a conclusion. Backward chaining is goal-driven and works from a goal back to the supporting facts.
What is an expert system shell?
An expert system shell is a ready-made inference engine and interface without a domain knowledge base. Examples include CLIPS, JESS and EMYCIN.
Test yourself
Flashcards
Click a card to see the answer.
Quiz
Questions generated by AI from the document: check the answers against the text.