Category: Artificial Intelligence

Directed acyclic graph(DAG)

operations
dependence edges

PRAM
memory
Scheduling: assigning ops to procs

the span of each DAG
line: O(n)
tree: O(log n)

Work-Span Laws
W(n)/D(n): Average available parallelism

for(iy=2; iy

Definition of Scripts
A causally coherent set of events.

1. Each event sets off, or causes, the next event.
2. The causal connections between events make sense.
3. The parts are actions or scenes in the world.

Restaurant Script
Script: restaurant
track: formal dining
props: tables, menu, check, money, F = food, P = place
roles: S = customer, W = waiter, C = cook, M = cashier, O = owner
entry: S is hungry, S has money
result: S has less money, O has more money, S is not hungry, S is pleased
scenes:

David went to the meeting with Ashok by car.

Thematic Role
verb : go
agent : David
coagent : Ashok
destination : meeting
conveyance : car

Prepositional Constraints
Preposition, Themantic Roles
by | agent, conveyance, location
for | beneficiary, duration
from | source
to | destination
with | coagent, instrument

e.g.
That was written by Ashok.
David went to New York by train
David stood by the statue.

Why do we need formal logic?
Soundness: Only valid conclusions can be proven.
Completeness: All valid conclusions can be proven.

Vertebrate -> Bird -> Eagle, Bluebird, Penguin
If an animal has feathers, then it is a bird.
If an animal lays eggs and it files, then it is a bird.

Ashok ate a frog.
subject: Ashok
object: a frog
time:
utensils:
object-alive: false
object-is: in-subject
subject-mood: happy

David ate a pizza at home:
subject: David
object: a pizza
time:
utensils:
object-alive: false
object-is: in-subject
subject-mood: happy

Angela ate lasagna with her dad last night at Olive Garden.
subject : Angela
object : lasagna
location : Olive Garden
time : night
utensils :
object-alive : false
object-is : in-subject
subject-mood : happy

Low Level <-> High Level
Hardware/Implementation Level(e.g. a brain, transister), Algrithm/Symbol Level(e.g. means-ends analysis, semantic networks), Task/Knowledge Level(e.g. selecting a pitch, playing baseball)

The layers of Watson: the physical computer searching and decision-making answering the inputted clue

Assumptions of a Cognitive Architecture
– Goal-oriented
– Rich, complex envrionment
– Significant knowledge
– Symbols and abstractions
– Flexible and function of the environment
– Learning

Architecture + Content = Behavior
Function for cognitive architectures: f:P* -> A
Percepts -> Action

SOAR
Procedural, Semantic, Episodic
-> Working Memory

A:B
x -> x :unchanged
y -> y :expanded
z -> z :deleted

lexically: nodes
structurally: directional links
semantically: application specific labels

Guards and prisonaers

similarity weight
5point for unchanged, 4 for reflected, 3 for rotated, 2 for scaled, 1 for deleted, 0 for shape changed

-intelligent agents have limited resources
-computation is local, but problems have global constraints
-logic is deductive, but many problems are not
-The world is dynamic, but knowledge is limited
-Problem solving, reasoning, and learning are complex, but explanation and justification are even more complex

Characteristics of AI Agents
-Agent have limited computing power
-Agent have limited sensors
-Agent have limited attention
-Computational logic is fundamentally deductive
-AI agents’ knowledge is incomplete relative to the world

input ->
Cognitive System
Metacognition
Deliberation:Reasoning, Learning, Memory
Reaction
-> output

Foundation
machine learning, semantic web, airplane autopilot, improvisational robots

import random
import numpy as np
import matplotlib.pyplot as plt

class Robot(object):
def __init__(self, length=20.0):
self.x = 0.0
self.y = 0.0
self.orientation = 0.0
self.length = length
self.steering_noise = 0.0
self.distance_noise = 0.0
self.steering_drift = 0.0

def set(self, x, y, orientation):
self.x = x
self.y = y
self.orientation = orientation % (2.0 * np.pi)

def set_noise(self, steering_noise, distance_noise):
self.steering_noise = steering_noise
self.distance_noise = distance_noise

def set_steering_drift(self, drift):
self.steering_drift = drift

def move(self, steering, distance, tolerance=0.001, max_steering_angle=np.pi/4.0):

if steering > max_steering_angle:
steering = max_steering_angle
if steering < -max_steering_angle: steering = -max_steering_angle if distance < 0.0: distance = 0.0 steering2 = random.gauss(steering, self.steering_noise) distance2 = random.gauss(distance, self.distance_noise) steering2 += self.steering_drift turn = np.tan(steering2) * distance2 / self.length if abs(turn) < tolerance: self.x += distance2 * np.cos(self.orientation) self.y += distance2 * np.sin(self.orientation) self.orientation = (self.orientation + turn) % (2.0 * np.pi) else: radius = distance2 / turn cx = self.x - (np.sin(self.orientation) * radius) cy = self.y + (np.cos(self.orientation) * radius) self.orientation = (self.orietation + turn) % (2.0 + np.pi) self.x = cx + (np.sin(self.orientation) * raidus) self.y = cy - (np.cos(self.orientation) * raidus) def __repr__(self): return '[x=%.5f y=%.5f orient=%.5f]' % (self.x, self.y, self.orientation) [/python]

Generating smooth paths

x0 … xn-1
xi

smoothing algorithm
yi = xi
optimize (xi-yi)^2 -> min (yi-yi+1)^2 ->min (original path)

from copy import deepcopy

def printpaths(path,newpath):
	for old, new in zip(path,newpath):
        print '['+ ', '.join('%.3f'%x for x in old) + \
               '] -> ['+ ', '.join('%.3f'%x for x in new) +']'

# Don't modify path inside your function.
path = [[0, 0],
        [0, 1],
        [0, 2],
        [1, 2],
        [2, 2],
        [3, 2],
        [4, 2],
        [4, 3],
        [4, 4]]

def smooth(path, weight_data = 0.5, weight_smooth = 0.1, tolerance = 0.000001):

	newpath = [[0 for row in range(len(path[0]))] for col in range(len(path))]
	for i in range(len(path)):
		for j in range(len(path[0]))
		newpath[i][j] = path[i][j]

	change = tolerance
	while change >= tolerance:
		change = 0.0
		for i in range(1, len(path)-1):
			for j in range(len(path[0])):
				aux = newpath[i][j]
				newpath[i][j] += weight_data * (path[i][j] - newpath[i][j])
				newpath[i][j] += weight_smooth * (newpath[i-1][j] \ + newpath[i+_][j])
				change += abs(aux - newpath[i][j])
	return newpath

printpaths(path,smooth(path))