(5th sem) AIML Chapter 1: Complete Concepts Guide
Chapter 1: Problems and Search -> Generated and Prepared By Thiruselvan (ThiruXD)
Part A: Introduction to Artificial Intelligence (Unit 1)
1. What is Artificial Intelligence?
Artificial Intelligence (AI) is the branch of computer science that makes machines perform tasks that normally require human intelligence.
These tasks include:
- Learning
- Reasoning
- Problem-solving
- Understanding language
- Perception (seeing, hearing)
- Decision-making
Term coined by: John McCarthy in 1956 at the Dartmouth Conference.
Two important definitions:
- John McCarthy: “AI is the science and engineering of making intelligent machines.”
- Elaine Rich: “AI is the study of how to make computers do things at which people are currently better.”
2. Five Main Concepts of AI
| Concept | Simple Meaning | Example |
|---|---|---|
| Learning | Improves with experience | Spam filter, Netflix |
| Reasoning | Draws conclusions from information | Medical diagnosis |
| Problem Solving | Finds solutions to complex situations | Route finding |
| Knowledge Representation | Stores knowledge in usable form | Rules, facts |
| Perception | Understands sensor data (image, sound) | Face recognition |
3. Goals of AI
- Create expert systems
- Put human-like intelligence into machines
- Make systems that can learn
- Enable machines to reason and decide
- Automate complex tasks
- Increase human productivity
4. Characteristics of AI
- Reasoning ability
- Learning capability
- Problem-solving power
- Knowledge representation
- Adaptability
- Decision-making
- Pattern recognition
5. AI vs Natural (Human) Intelligence
| Feature | Human Intelligence | Artificial Intelligence |
|---|---|---|
| Origin | Biological | Man-made |
| Learning | Experience + emotions | Data-driven |
| Creativity | Very high | Limited |
| Speed | Moderate | Extremely fast |
| Memory | Limited | Very large |
| Emotions | Present | Absent |
| Common sense | Strong | Weak |
6. Applications of AI
- Healthcare: Diagnosis, medical imaging, drug discovery
- Education: Personalized learning, intelligent tutoring
- Agriculture: Crop monitoring, pest detection
- Finance: Fraud detection, credit scoring, trading
- Robotics: Industrial robots, autonomous vehicles
- NLP: Chatbots, translation, speech recognition
Part B: AI Problems and Problem Spaces (Unit 2)
1. What is an AI Problem?
A problem that needs intelligent behaviour (reasoning, learning, planning, perception) to reach a goal.
Characteristics of AI Problems:
- Complex (many possibilities)
- Uncertain (incomplete information)
- Dynamic (environment can change)
- Knowledge-intensive
- Goal-oriented
Types of AI Problems:
- Search Problems (maze, path finding)
- Reasoning Problems (medical diagnosis)
- Planning Problems (robot navigation)
- Learning Problems (image classification)
2. Problem Space
A problem space is the complete set of all possible states that can occur while solving a problem.
Four main components:
| Component | Meaning | Example (Route Finding) |
|---|---|---|
| Initial State | Starting condition | Bengaluru |
| Goal State | Desired final condition | Mysuru |
| Operators | Actions that change one state to another | Travel by road |
| State Space | All possible reachable states | All cities and routes |
How it is represented:
- Usually as a graph
- Nodes = States
- Edges = Operators (actions)
Importance:
Almost every AI problem (games, robots, planning, scheduling) is solved by searching through a problem space.
Part C: Search Techniques (Unit 3)
Search is the process of exploring the problem space to find a path from the initial state to the goal state.
1. Uninformed Search (Blind Search)
These methods do not use any extra knowledge about how close a state is to the goal.
A. Breadth-First Search (BFS)
- Explores level by level
- Uses a Queue (FIFO)
- Finds the shortest path (in terms of number of steps)
- Complete and optimal (when cost is uniform)
- Disadvantage: Needs large memory
B. Depth-First Search (DFS)
- Goes as deep as possible along one path
- Uses a Stack (LIFO) or recursion
- Less memory needed
- Disadvantage: May get stuck in infinite paths, not optimal
Comparison of BFS and DFS
| Feature | BFS | DFS |
|---|---|---|
| Data Structure | Queue | Stack |
| Path Found | Shortest (no. of steps) | Not necessarily shortest |
| Memory | High | Low |
| Completeness | Yes | No (in infinite spaces) |
| Optimality | Yes (uniform cost) | No |
Part D: Heuristic Search Techniques (Unit 4)
Heuristic search uses extra knowledge (rules of thumb) to guide the search towards the goal faster.
1. What is a Heuristic?
A heuristic is an educated guess or rule of thumb that helps estimate how close a state is to the goal.
Heuristic Function h(n) = estimated cost from current state n to the goal.
2. Important Heuristic Techniques
A. Generate and Test
- Generate a possible solution
- Test if it is correct
- Repeat until success
- Simple but can be slow
B. Hill Climbing
- Always moves to a better neighbouring state
- Like climbing a hill by always going upwards
- Fast but can get stuck in local maxima (small hills)
Variants of Hill Climbing:
- Simple Hill Climbing
- Steepest Ascent Hill Climbing
- Stochastic Hill Climbing
C. Best-First Search
- Uses an evaluation function f(n)
- Always expands the most promising node first
- More intelligent than BFS or DFS
Part E: Problem Reduction and Constraint Satisfaction (Unit 5)
1. Problem Reduction
Breaking a big complex problem into smaller sub-problems that are easier to solve.
Advantage: Makes large problems manageable.
2. Constraint Satisfaction Problems (CSP)
A CSP has three components:
- Variables (things we need to assign values to)
- Domains (possible values for each variable)
- Constraints (rules that must be satisfied)
Example: Map colouring, Sudoku, exam timetable, job scheduling.
Techniques to solve CSP:
- Backtracking Search
- Forward Checking
- Constraint Propagation
3. Means-Ends Analysis
A powerful problem-solving strategy:
- Compare current state with goal state
- Find the difference
- Choose an operator that reduces the difference
- Repeat until goal is reached
Used in planning systems and expert systems.
Complete Chapter Summary (Must Remember)
- AI = Making machines intelligent (learning, reasoning, solving problems).
- AI Problems are complex, uncertain and goal-oriented.
- Every AI problem is represented as a Problem Space (Initial state + Goal + Operators).
- Search is the main method to find a solution in the problem space.
- Uninformed Search: BFS (shortest path) and DFS (less memory).
- Heuristic Search: Uses extra knowledge (Hill Climbing, Best-First Search).
- CSP = Variables + Domains + Constraints (solved by backtracking).
- Means-Ends Analysis reduces the difference between current and goal state.