MAINSIT COURSEWORK 1

Introduction to AI – Assessment 2023/24

Learning Outcomes

• LO1 ‐ Gain knowledge and understanding of artificial intelligence

• LO2 ‐ Be able to work effectively in teams to design an intelligent system

• LO3 ‐ Demonstrate ability to communicate effectively on the topic of AI

• LO4 – Be able to develop a simple prototype from a brief using existing skills

Assignment 1 (25%):

“Presentation of Research” 25% - This is a synthesis of your knowledge in the field of AI. Please submit
your weekly mind maps/diagrams with 1 major synthesis of the topics covered.

This must be attempted individually.

Submission to include:

1. One document to include 10 pages of “mind-map” drawings, include labels, explanations, links
as required (10 weeks, 10 diagrams)
2. All submissions will be graded using the following criteria:
• Presentation of Research 20%
• Depth of knowledge [LO1] 30%
• Synthesis of information [LO1] [LO3] 30%
• Presentation (clarity) [LO3] 20%
To receive

A : all keywords and connections clearly expressed + more depth in some areas that interest you +
synthesis that shows links between topics

B: all keywords and connections clearly expressed + synthesis that shows links between some topics

C: keywords and connections clearly expressed but not complete + attempt at synthesis of topics

D: keywords and connections attempted

E: key words with limited connections

To receive

A: Excellence in all aspects

B: Good working application with clear documentation showing references

C: Working prototype with documentation showing references

D: Basic working prototype with documentation showing references

E: Attempt at prototype with documentation showing references

Marking Scheme for Assignment 1 (25%)

PRESENTATION OF RESEARCH (10%) All 10 mind maps present, each covers 1 10

lesson
DEPTH OF KNOWLEDGE (50%) Each mind map explores the topic/lesson 20
to a sufficient depth, decomposes the
main topic to sub topics with clear textual
annotations
Suitable images and diagrams are given 20
Relevant and valid hyperlinks (at least 3 10
per diagram)
SYNTHESIS (30%) Components (text, images, labels, 30
hyperlinks etc.) are connected in a
meaningful way to provide an effective
overview of the topic
CLARITY (10%) Provides a clear overview of an AI topic at 10
a glance
Mind Map 01 – Artificial Intelligent

Mind Map 01- Outline

• Introduction to Artificial Intelligence

• What is Artificial Intelligence
– Four Main Approaches
• Think Human
• Act Human
– Turing Test
• Alan Turing
• Can a Machine Think?
• The Imitation Game
– NLP, Knowledge Representation, Automated Reasoning, Machine Learning
– Computer Vision (Perception)
– Robotics (Manipulation, Manifestation)
• Think Rational
– Study Underlying Principles
– Strong AI - Computer Can Think
– Cognitive Science
• Introspection
• Psychological Experiments
• Brain Imaging
• Act Rational
– Logic (Started with Aristotle)
– Agents
• Autonomous
• Persistent
• Perceive Environment
• Adapt to Change
• Create and Pursue Goals
– Famous Problems and Concepts
• The Turing Test
• The Chinese Room
• Consciousness
– Subjectivity
– Self-awareness
– Sentience
– Sapience
– State of the Art
 • Game Playing
• Robotic Vehicles
• Speech Recognition
• Autonomous Planning and Scheduling
• Spam Fighting
– Disciplines
• Economics (Game Theory)
• Maths (Logic, Probability, Algorithms, Computation)
• Philosophy (Formal Rules, Knowledge and Action)
• Neuroscience (Consciousness from Simple Cells)
• Computer Engineering (Intelligence + Artifact, Speed and Capacity)
Mind Map 02 – Agent

Mind Map 02 - Outline

• Agents
– Example: Vacuum Cleaner World
• Percepts: location and status (e.g., dirty)
• Actions: move left, move right, suck dirt, do nothing
– Rational Agent
• Does the “right thing”
• Evaluates environment state, not agent state
• Performance Measure
– Determines success
– Example: dirt cleaned in 1 hour, clean floor rewards, penalties for
time/energy used
• Depends on
– Performance measure
– Prior knowledge of environment
– Actions it can perform
– Percept sequence to date
• Rationality vs. Omniscience
– Rational agents learn and gain autonomy
– Information gathering, exploration, learning
– Task Environment
• Performance Measure
• Environment
• Actuators
• Sensors
• Example: Autonomous car
– Task Environment Properties
• Fully / Partially Observable (Unobservable)
• Deterministic / Stochastic
• Single / Multi-Agent
• Episodic / Sequential
• Static / Dynamic (Semi-Dynamic)
• Known / Unknown
• Discrete / Continuous
– Intelligent Agents
• Act like a human
• Think like a human
• Think rationally
• Act rationally
– What is an Agent?
• Perceives environment using sensors
• Acts on environment using actuators
• Hardware: robot
• Software: softbot
– Sensors: key inputs, data packets
– Actuators: screen display, write files, send data
– Percept
• Perceptual inputs
• Percept sequence
• Choice depends on chunk of percept sequence
– Agent Function vs. Agent Program
• Agent Function
– Abstract - Describes behavior
• Agent Program
– Concrete implementation using code
• Agent Architecture
– Structure supporting the program
– Types of Agents
• Simple Reflex Agent
– Condition - Action Rule (e.g., if car-in-front is braking, then initiate braking)
• Model-Based Reflex Agent
– Uses model of world
• Goal-Based Agent
– Uses search and planning
• Utility-Based Agent
– Uses utility function
• Learning Agents
– Learning element
– Performance element
– Critic
• Provides feedback
– Problem Generator
– Environment Interaction
• Sensors and Actuators
Mind Map 03 - Goal-Based Agents

Mind Map 03 – Outline

• Goal-Based Agents
– Pathfinding
• Traffic Control
– Example: City Traffic Simulator
• Games
– Problem-Solving - Having Goals
• Goals Help Organize Behavior
– Limit Objectives
– Limit Actions Agent Needs to Consider
• First Step: Goal Formulation
– Based on Current Situation
– Based on Performance Measure
• SEARCH
– Looks for Sequence of Actions to Reach Goal
– Well-Defined Problem
• Initial State
– Example: in (London)
• Set of Possible Actions
– For State s, Actions(s) = { go(Norwich), go(Cardiff), go(Manchester) }
• Transition Model
– Result(s, a) - State that Results from Action a in State s
• Example: Result( in(London), go(Norwich) ) = in(Norwich)
• Goal Test
– Example: am I in Edinburgh yet?
• Path Cost Function
– Example: how long?
– State Space
• Network or Graph
– Path = Sequence of States Connected by Sequence of Actions
• Historically Representing Semantic Networks
• State = Node
• Transition = Edge
• Nodes and Edges
– G = {N, E} - Set of Nodes Linking Set of Edges
• Representation of Data
– Each Node = Integer
– Each Edge Connects Two Nodes
• Weighted Edge
 – Cost Involved (e.g., time, distance, effort)
• Digraph
– Directed Edges with Different Costs
– Examples of Contexts
• Toy Problem and Real-World Problem
• Graph = Network
– Linked-in Connections
– Tile-Based Game (grid)
– Website Index
– Circuit
– Human Proteins (dependencies)
• Travelling Salesman Problem
– Practical Uses: routing trucks, material handling, genome sequencing
– Complexity Increases Exponentially
– Types of Searches
• Get to the Target
• Visit Every Node (in what order?)
• Find Best Path to Target
• Best Path to Target Using Least Effort
– Depth First Search (DFS)
• Follow Each Node to Its Limit
• Reverse When Dead End
• Keep Going If Unexplored
• Delve Deep into the Graph Space
• If Graph is CONNECTED, Guarantee All Nodes and Edges Visited
– Breadth First Search (BFS)
• Explore Each Node Radiating Out from Start
• Do 1 Step Out in Every Possible Direction, then 2 Steps, etc.
• Skip Edges Already Explored
• Guarantees Shortest Path to Target
– Visual Example: PathFinding.js
– Best First Path Search
• A* Search
– Improvement: Introduces a Heuristic
– Cost of Each Node = Cost of Edge + Cost of Previous Node + Estimated Cost
to Reach Target
Mind Map 04 – Pathfinding Algorithms

Mind Map 04 – Outline

• Pathfinding Algorithms
– State Space
• Representation of the problem space in a graph or grid form
– Search Process
• Is Current State a Goal?
• If Not, EXPAND State
– Select One Option, Save Others for Later
– Frontier (Open List): Set of Leaf Nodes
• Parent Node
• Child Node
• Leaf Node
– Search Algorithm Infrastructure
• Data Structure: Queue = Lookup Table
• Node Information
– Node State (Current Location)
– Node Parent (Previous Location)
– Node Action (Possible Next Steps)
– Node Path Cost (Total Cost to Current Location)
– Graph Search
• Useful Representation: Grid
• Example: Pathfinding on Grids
– Informed Search (Uses Heuristic)
• Best-First Search
– Uses Evaluation Function f(n)
• Heuristic h(n): Estimated Cost from n to Goal
• Greedy Best-First Search
– Expands Node Closest to Goal
• Quick but Non-Optimal
• A* Search
– Combines Path Cost and Heuristic
– f(n) = g(n) + h(n)
• g(n): Path Cost from Start to n
• h(n): Estimated Cost from n to Goal
– Optimal and Complete
– Example: Vacuum Cleaner World
– Heuristics
• Underestimate Guarantees Optimal Path
• Examples
 – 8 Puzzle
• h1 = Number of Misplaced Tiles
• h2 Manhattan = Sum of Distances from Goals
– Manhattan, Diagonal, Euclidean
– Slime Mould
• Simple Organism for Efficient and Optimal Networks
• Example: Designing Transportation Networks
– Search Tree
• Branch = Action
• Node = State
– Initial State: Arad
– Nodes: Timisoara, Sibiu, Zerind, Fagaras, Rimnicu
– Warnings
• Forgetting History Leads to Repeating It
• Loopy Paths = Infinite Searches
• Maintain an Explored Set
– Frontier Separates Explored and Unexplored Regions
– Measuring Performance
• Completeness: Guarantees Finding a Solution
• Optimality: Lowest Path Cost
• Time Complexity: Duration
• Space Complexity: Memory Requirement
– Uninformed Search (Blind)
• Breadth-First Search (BFS)
– FIFO (First In, First Out)
– Memory Intensive
• Uniform Cost Search
– Expands Node with Lowest Path Cost
– Changes Order of Queue
• Depth-First Search (DFS)
– LIFO (Last In, First Out)
– Backtracking Search Uses Less Memory
• Depth-Limited Search
– Predetermined Limit
– Avoids Infinite Loops
• Iterative Deepening Depth-First Search
– Gradually Increases Depth Limit
• Bidirectional Search
– Dijkstra’s Algorithm
• Shortest Path in Weighted Graphs
• Builds on BFS by Adding Edge Weights
• Uses Edge Relaxation
 • Example: Finding Shortest Path
– Genetic Algorithms
• Measure Fitness of Each Possibility
• Determine Probability of Selection
• Randomly Match Two Parents
• Swap Match (Like DNA) for Offspring
• Random Mutation
– Example: Pathfinding in Games
– A* Tutorial Links
• Redblob Games
• Stanford Game Programming
• Policy Almanac A* Tutorial
• Cat and Bone Tutorial
• Wikipedia A* Search Algorithm