Transcript 29 September, 2 October 2008

Bioinspired Computing
Lecture 1:
Overview & Biased History
Objectives
On completion of this module, students should be able to:
•understand both the appeals and limitations of natural
systems as the inspiration for artificially intelligent systems;
•understand of some of the many artificial intelligence
techniques that have been inspired by natural systems (eg.
artificial neural networks, evolutionary computing, ant-like
systems);
•implement one or more of these systems to solve a particular
problem (eg., using an artificial network to control a simple
simulated robot).
2
Syllabus
Introduction, history and philosophy of bio-inspired
computing; artificial neural networks for pattern
recognition; artificial neural networks for control; multiagent systems and swarm intelligence; bio-inspired
graphics and art; evolutionary design; coevolutionary
design; simulation modelling in biology and beyond;
applications of bio-inspired computing.
3
Today ….
Overview talk
Outcome
• Introduction to the module
• Insight in why the field is attractive to many people
• First review of some of the characteristics that bioinspired approaches share
4
Lecturing Staff
• Marc de Kamps ([email protected])
– Started in high energy physics
– Postdoc in cognitive modelling
• Neural networks
• Spiking neurons simulation
• Vision, attention (in vision), neural representation of language
• Slides based on last year’s lectures
– A long string of original contributions over the years: Seth
Bullock, Jason Noble, Netta Cohen
– Slides will be handed out
– All slides currently available, but these will be updated from
last year’s version as the weeks progress (so don’t assume
things will be exactly the same as last year!)
• Next year: third year module
• prereq.: maths
5
Timetabling
This module has two lecture slots
Monday 13:00 – 14:00 Roger Stevens LT02
Thursday 12.00 - 13:00 Roger Stevens LT10
For postgraduates there are extra tutorials
Thursday 11.00 – 12.00 E. C. Stoner 8.203
will look for an alternative
Demonstration sessions will only be given some weeks
- notified in advance in lecture and/or VLE.
We need to find a slot for demos !
WATCH THE VLE FOR UPDATES
6
Resources
• Course Website: http://www.comp.leeds.ac.uk/ai33
– Lecture Slides
– Module Outline
– Reading Lists
– Assignments
– Useful Links
• The resources are on the website and not on the VLE
• Reading available in library, or via links on course page.
• Each other
– Talk about the material.
– Talk about the assignments.
– Help each other; feel free to work together, but
– Submit only you own personal original work.
7
Courseworks
• Coursework 1: random processes
– Set: asap
– No special bic knowledge required
– Due: 17/10/2008
• Coursework 2:
– Set: 20/10/2008
– Due:
– Required agents, genetic algorithms
• Coursework 3 (postgraduates only): viva
– Date to be agreed
8
Module oveview
week
Topic 1
Topic 2
1
Intro BIC
Intro BIC
2
Swarm/ant Int.
Swarm/ant. Int
3
Neurons and brain
Perceptron
4
MLP (Backprop)
GA: introduction 1
5
GA: introduction 2
NN: Recurrent NNs
6
NN: Hopfield networks
GA: coevolution
7
GA: coevolution
NN: SOMs (Kohonen)
8
Recap – differences and
communalities of BIC
Guest lecture: C. Elegans
9
DNA computing
Von Neumann machines
10
Human visual system
High level cognition
9
What is this module all about?
Bio-inspired computing
Biological computation
Artificial Intelligence
10
What is Bio-inspired computing?
• What is computing?
• Answer can be given in some way: Universal Turing
Machine
• Example: compute planet trajectories
• Fixed recipe
–
–
–
–
Chop up state space
Define mapping
Write program
Run it -> Done
• Since ENIAC we’ve been upgrading the UTM
• Strong AI
11
1672
12
1672
13
1672
14
1673
15
1673
16
17
The Birth of AI
In the 1940s Alan Turing was already speculating on…
1. …the possibility of general computer intelligence –
abstract games: good initial tasks ‘requiring little
contact with the outside world’…
2. …the potential for a computer chess player –
search algorithms to used to find good moves…
3. …a way of deciding whether a computer was
intelligent – the Turing Test is a totally disembodied
interrogation (but a somewhat situated one)…
Artificial Intelligence is an attempt to simulate reasoning as:
abstract, formal, disembodied, symbol manipulation.
Note that Turing was also interested in BiC – “The chemical
basis of morphogenesis” (52)
18
Criticism of AI
• Sometimes unfair:
– "As soon as someone gets a computer to do it,
people say: 'That's not what we meant by
intelligence.' People subconsciously are trying to
preserve for themselves some special role in the
universe."
– - Michael Kearns
– The AI Effect: "The great practical benefits of AI applications and
even the existence of AI in many software products go largely
unnoticed by many despite the already widespread use of AI
techniques in software. This is the AI effect. Many marketing people
don't use the term 'artificial intelligence' even when their company's
products rely on some AI techniques. Why not?"
• See http://aaai.org/AITopics/html/aieffect.html
19
SHRDLU
By 1972, Terry Winograd’s invented a
simulated robot arm surrounded by blocks
of various shapes and colours on a table.
SHRDLU could…
•
•
•
•
understand natural language instructions
ask questions to disambiguate these instructions
act & reason in a simulated “blocksworld” environment
answer questions about the world & its own reasoning
In Winograd’s words, it was “a computer program which
‘understands’ language in a limited domain.”
SHRDLU’s algorithms carried out model building,
search, planning and logical deduction.
See for example: http://hci.stanford.edu/~winograd/shrdlu/
20
A Conversation with SHRDLU
> Pick up a big red block.
OKAY.
> Grasp the pyramid.
I DON’T KNOW WHICH PYRAMID YOU MEAN.
> What does the box contain?
THE BLUE PYRAMID AND THE BLUE BLOCK.
> I own blocks which are not red, but I don’t own
anything which supports a pyramid.
I UNDERSTAND.
> Do I own the box?
NO.
(adapted from Dreyfus’ 1979 What Computers Can’t Do)
21
Is that really how our brain works?
John Von Neumann, father of modern high-speed
computers also thought about neuro-computation and
tried, for the first time, to construct a meaningful
comparison between brain and computer power.
Von Neumann argued that the brain must employ digital
computation. Figuring in the number of neurons,
connections, and estimates of computational speed and
statistical noise in the brain, he then concluded that the
brain could not be explained by logic alone.
In fact, he apparently postulated (and began writing) an
alternative theory but died soon after.
22
The manuscript (published post mortem) ends as follows:
“The Language of the Brain is Not the Language of Mathematics …
whatever language the central nervous system is using, it is
characterized by less logical and arithmetical depth than what we
are normally used to … Consequently, there exist here different
logical structures from the ones we are ordinarily used to...
… whatever the system is, it cannot fail to differ considerably from
what we consciously and explicitly consider as mathematics.”
(John Von Neumann, The Computer and the Brain, 1958.)
In a recent commentary, Harold Morowitz writes:
“Von Neumann challenged the validity of the underlying
conceptualizations we use to study the brain and compare it with
computers. Yet, what is surprising, given the great esteem for John
Von Neumann, is that no one has taken up on his argument and
fully developed its consequences in the mind versus artificial
intelligence arguments that had been waging the last few years.” 23
Criticism of AI
(see eg. Pfeifer, “Understanding Intelligence”)
• Frame problem
• Symbol grounding problem
24
Frame Problem
(McCarthy & Hayes, 1969)
Checkout: http://plato.stanford.edu/entries/frame-problem
• Predicates which can depend on time t are called
fluents
• A situation where a door is closed, the light is off and
and the door is opened at t = 1 can be represented
by:
┐open(0)
┐on(0)
true →open(1)
• Direct expression of what is known, but insufficient to
correctly draw consequences
25
Frame Problem
• The following situation is logically consistent with the
known situation:
┐open(0) open(1)
┐on(0) ┐on(1)
• The following too:
┐open(0) open(1)
┐on(0) on(1)
• This makes no sense causally, but perfect sense
logically
• A superficial solution requires frame axioma’s:
on(0) ≡ on(1)
26
Frame Problem
• To formulate frame axioms for every condition, action
combination that must not change is not an option
• Solution possible but subtle, unlikely for living
creatures
• “The frame problem in philosophy is therefore the
problem of how a rational agent bounds the set of
beliefs to change when an action is performed.”
(Wikipedia)
• Biological creatures (including humans) do not seem
overly troubled by it …
27
Symbol Grounding Problem
(Searle 1980; Harnard 1990)
• In AI rules are used to operate on symbols
• The rules operate independent of the
meaning of symbols
• This is not a problem as long as there is a
human around to make sense of the symbols
• Powerful formal reasoning
• Difficulties with interpretation
• Computer vision, speech recognition,
interpretation still difficult
28
Chess vs. Football
Chess
• Discrete
• Full Information
• Single Opponents
• Turn Taking
• Limited Options per Turn
• Intellectual, disembodied
• Optimal Strategy Exists?
• Demands General Intelligence?
• Formal, Analytical, Symbolic
Football
• Continuous
• Partial Information
• Heterogeneous Teams
• Continuous Confrontation
• Unlimited Options
• Physical, embodied
• No Optimal Strategy?
• Demands Specialist Skills?
• Dynamic, Physical, Reactive
•Can the problems faced by footballers be solved
through symbol processing and heuristic search?
29
•Commentary v. playing?
“Intelligence w/out Reason”
Rodney Brooks (“Intelligence Without Reason”): Critic of
the AI approach & strong proponent of embodiment and
situatedness in bioinspired computing (BIC).
AI, he claims, followed the abstract route due to
technological gaps in the 40s & 50s.
Today (1991), he says, it’s time to move on.
Brooks recognised that life-like systems are often
intelligent to some degree, yet reasoning is primarily
considered to be a human attribute. Rather than modelling
complicated human behaviour, why not start simple?
30
“There are a number of key aspects characterizing
this style of work
• [Situatedness] The robots are situated in the world - they do not
deal with abstract descriptions but with the here and now of the
world directly influencing the behavior of the system.
• [Embodiment] The robots have bodies and experience the
world directly their actions are part of a dynamic with the
world and have immediate feedback on their own sensations.
• [Intelligence] They are observed to be intelligent - but the
source of intelligence is not limited to just the computational
engine. It also comes from the situation in the world, the signal
transformations within the sensors, and the physical coupling
of the robot with the world.
• [Emergence] The intelligence of the system emerges from the
system's interactions with the world and from sometimes
indirect interactions between its components - it is sometimes
hard to point to one event or place within the system and say
that is why some external action was manifested.”
(Brooks 91)
31
Why Not The Whole Iguana?
(Dennett 78)
• Traditional computing is task-oriented (vertical).
• To survive, animals have to be good across the board!
Walking
Sex
Memory
Chess
Iguana
Cricket
Horizontal
Vertical
Human
Ant
Rather than build parts of human intelligence, why not
build an entire much simpler intelligence?
32
Performance without CPU
• Locomotion
• Examples of dynamic movers:
http://mms.tudelft.nl/dbl/download/video/
(museonside.mpg was shown in the lecture)
• Compare:
http://world.honda.com/ASIMO/history/techno
logy.html
33
How do biological systems deal with these issues?
Biological performance is
• dynamic
• flexible, adaptive
• robust, noise/defect tolerant
34
http://dictybase.org/Multimedia/index.html
http://dictybase.org/Multimedia/motility/gerisch1.avi
Free-ranging
amoebae
Slime moulds
aggregation
fruiting body
migratory slugs
mound
When food is plentiful, amoebae live & multiply independently.
When food is scarce, they secrete a chemical signal that
attracts amoebae towards each other. As cells aggregate
they form a mound, then a slug, and eventually fruiting bodies.
The slug can migrate to a more desirable location.
When a slug reaches an appropriate place, the cells
differentiate to form spores and a stalk. The fruiting body
consists of mature spore cells on top of dead stalk cells.
These spore cells fall off, starting their own colonies.
35
Collective behaviour in
the slime mould
36
http://herbie.ucsd.edu/~levine/dicty.html
Chemical waves in slime mould
37
DNA
preserving fortunate accidents
38
Powerful idea
• Does not really depend on actual
mechanism
• Can be used in artificial systems?
• Yes, evolve hardware, programs
• Good search technique!
39
The slime mould…
• Is no more than a collective manifestation of amoeba
• It self-organised in the face of duress (food deprivation,
pressure for self-preservation/self-replication).
• It is completely decentralised/distributed: There is no leader.
• Each amoeba follows simple rules.
• Individual amoebas are not reliable.
• The amoeba is adaptive; its function is context-dependent.
• Interactions among different levels of organisation
• The solution is defined in terms of the system at large
(slime mould and its survival, not individual amoeba).
40
Performance without CPU (2)
• EU project hydra
• http://hydra.mip.sdu.dk/home.html
• ATRON hardware videos
http://hydra.mip.sdu.dk/Videos/atronHWvideos/s2c.avi
• Self-configuring BOEING:
http://hydra.mip.sdu.dk/Videos/CA_videos/747_slow.mpg
41
Some unifying concepts/inspirations
• Eliminate pre-imposed hierarchies, eliminate leaders
• Allow a decentralised (distributed) approach and parallelism
• Allow simple rules for cooperation among components
• Allow interactions among different levels of organisation
• Define solutions in terms of system-wide variables
Computers need not be as complex as biological
machines. By incorporating key principles we hope to
achieve much improved functionality.
42
What might computer scientists
learn from biological systems?
Some limitations of today’s computers:
• Computers crash! (OS usually to blame)
• The complexity of computer programs is limited. The
biggest programs are less complicated than the simplest
biological cell.
• Computers don’t self-replicate.
• They don’t self-organise.
• They don’t fix themselves.
• Computers are always right (i.e. they follow their
programs correctly), but don’t always give the answers
we want to know. Computers are unforgiving.
43
Potential implications:
Pretty soon computers will miniaturise to molecular scales.
This transition will require
• noise/defect-tolerance
• self-assembly/self-organisation at the hardware level
Software will need to cope with ever-increasing complexity.
Can software self-organise? Self-evolving software is already
in use both in traditional computing & robotics.
Computer systems are networked in massive complex and
dynamic architectures. Distributed approaches to managing
networks/grids are being implemented. Specifically, ant
algorithms are used in re-organising internet connectivity in
the face of node failures.
44
Properties of biological systems
• Collective behaviour
• self-organisation, self-assembly and self-repair
• self-replication/reproduction
Emergence: Organisation of structure & function is
achieved by the system as a coherent, organic and
autonomous entity, even though this whole consists of
components which are themselves autonomous.
The whole is greater than the sum of the parts.
45
Collective computations finds
reasonable solutions
• Biological creatures are sometimes
faced with very hard problems
• Solution does exist, but takes
impossible time to solve
• Collective action sometimes produces a
solution that is reasonable in short time
46
The problem: Directed Hamiltonian Path
• Given a graph with directed edges, find a Hamiltonian Path,
i.e. a path which starts at one node, finishes at another, and
goes through all other nodes exactly once.
• Variant of the travelling salesman problem where all roads
are the same length:
• A salesman wants to travel over a fixed set of roads
between N different towns without ever coming back to a
town he has already visited.
Find a sequence of fights which
goes from Fresno to Boston
landing at all other airports
exactly once.
47
How hard is it?
A P problem is one which can be solved in polynomial time, basically at a rate which
is some fixed power of N, where N is the size of the problem. An NP hard problem is
one for which no one knows an algorithm which does not take exponential time (2 or
some other power of a number > 1).
Methods taking exponential operations can work out whether or not such a route
exists and report it if it does, but even for small problems they take too much time to
be practical.
Any NP problem can
be transformed to
another in P time – so
solve one efficiently
and can solve any NP
problem efficiently!
48
Emergent solutions
• We will look at solutions that emerge
from systems of interacting basic
components in:
– Neural Networks (2x; different!)
– Swarm Intelligence
– DNA computing
49
Open questions
• Can human cognition be understood this
way?
• Is human cognition a dynamical process,
which self-organizes, is emergent, …?
• Does the brain have executive modules?
• There are manifest differences: e.g. symbols
can not be copied
50
Examples
• Collective behaviour
• self-organisation, self-assembly and self-repair
• self-replication/reproduction
• emergence
What are the underlying principles
that give rise to this behaviour?
51
Pattern formation in nature
52
From Pattern Formation to Computing?
Conjecture:
If principles of pattern formation underlie the development
of a foetus, why not the development of program or an
electronic circuit?
Computers need not be as complex as biological machines.
Maybe by incorporating key principles from biology we can
already achieve much improved functionality.
First baby steps:
Pattern formation could be useful if…
• We can extract minimal principles to mimic it.
• We can harness the patterns for useful computation.
53
Why do we care?
• Computer hardware is “hard”, but must it be?
• What about ad-hoc configurations of computer and
communications networks?
• Pattern formation is an example of parallel processing
that is highly versatile, adaptive, and robust. Can we
simplify existing algorithms using similar concepts?
• Simulations of natural pattern formation processes are a
growing industry for art, movies, and even music.
54
Lindenmayer Systems
L-systems define sets of local rules for making patterns.
Requirements: an initial term and a set of rules.
A simple rewriting system:
Rule: A  AB
would develop as follows:
A … AB … ABB … ABBB…
Notice: early strings are
sub-components of later
strings. Also, strings are
self similar at all levels.
Adding rule B  BA, gives:
A … AB … ABBA …
ABBA BAAB …
ABBA BAAB BAAB ABBA …
ABBA BAAB BAAB ABBA
BAAB ABBA ABBA BAAB …
ABBA BAAB BAAB ABBA
BAAB ABBA ABBA BAAB
BAAB ABBA ABBA BAAB
ABBA BAAB BAAB ABBA …
55
Geometric Rewriting Systems
Replace letters with geometries: Grow pictures, not sentences…
Turtle graphics approach: Imagine a turtle that can only understand
three commands: F (move forward a distance d, drawing a line); +
(turn left through ao), - (turn right through ao).
Set d=1, a=90. Give turtle initial string of commands (say F-F-F-F).
Then, apply set of rewrite rules again and again and again…
Example rewrite rule:
F  F-F+F+FF-F-F+F
(The resulting patterns will
be examples of quadratic
Koch islands)
56
From lines to trees
To generate more life-like shapes…
First, we need a way of representing branches. To
do this, Lindenmayer employs a bracketing notation:
[ Before carrying on, push the current state of the
turtle onto the top of a pushdown stack (i.e.,
remember the current position and orientation of
the turtle for later).
] Before carrying on, pop the state from the top of
the stack and make it the current state of the
turtle. This will often move the turtle to a
different (earlier) part of the shape, or rotate it, or
perhaps alter its state in some other way.
How does stack system affect L-system’s behaviour?
57
Branching structures & self-similarity
Imagine a simple L-System featuring brackets…
Initiator:F Rewrite Rules:F  F [+F] [-F] F ; a=30o
0: F
1: F[+F][-F]F
2: F[+F][-F]F
[+F[+F]-F]F]
[-F[+F]-F]F]
Note rescaling
F[+F][-F]F
3: etc.
Recursion + branching = tree-like structures
Tree-like structures and other shapes that look the same
on every scale, are called self-similar systems. These
self-similar structures are simple examples of fractals. 58
Exploring Simple L-Systems
It isn’t hard to discover initial states,
rules, and constants which produce
recognisably plant-like structures.
However, when generalised to three
dimensions, coupled with appropriate
textures and colouration, and altered
to include leaves, flowers, etc., Lsystems have been used to generate
some truly remarkable life-like images.
Image courtesy M. Masse
Images authored by V. Nový
59
Overview of next weeks
60
Topics in bio-inspired
computing
•
•
•
•
•
•
•
Multi-agent systems and Swarm Intelligence
Artificial neural networks
Evolutionary design and genetic algorithms
Co-evolutionary design
Artificial life
Robotics and control
Interfacing biology with silicon
61
Food foraging in Ant colonies
A computer simulation of an ant colony performing an efficient
search: Blue spot in the middle is an ant nest; other 3 spots
represent food sources. Ants (red dots) use chemical signals
(green) to find the shortest path to the food and alter their
signals as the food is depleted.
Ant algorithms are implemented in many real-world systems.
http://education.mit.edu/starlogo/
62
http://education.mit.edu/starlogo/samples/ants.htm
System wide variables
(Felleman & van Essen, 1991)
63
Interaction between hierachies
(Felleman & van Essen, 1991)
64
Self-organisation and interaction
with environment
• Orientation columns human cortex
65
Emergence
66
Extraction essential principles
• Feedforward perceptron networks
67
Extraction essential principles
• Working memory
68
Overview end
69
What is BIC and what does it want to achieve?
Bio-inspired
computing
Biological
computation
or
Artificial
Intelligence
70
Bioinspired programming
Some of the best bioinspired applications to
computing are the ones we would never associate
with biology.
Perhaps the most successful and pervasive
bioinspired application is…
Object-Oriented Programming
71
Alan Kay
by Scott Gasch
While studying at the University of Utah he learned about the
innovative Sketchpad program developed by Ivan
Sutherland and began programming in Simula. Borrowing
ideas from this and other systems, as well as from his
background in biology and mathematics, he formulated his
"biological and algebraic analogy.“
Kay postulated that the ideal computer would function like a
living organism; each "cell" would behave in accord with
others to accomplish an end goal but would also be able to
function autonomously. Cells could also regroup
themselves in order to attack another problem or handle
another function.
http://ei.cs.vt.edu/~history/GASCH.KAY.HTML
72
How it works
• Autonomous cells
• Messages (data, sender & receiver addresses)
• Operations (contained in message)
• Cell differentiation (context-dependent functionality)
What good is this?
‘Building’ programs the way civil engineers design buildings.
programmers can create objects to mimic generic conceptual
building blocks: No need for a new language with each
application.
Inspiration & technical basis for the MacIntosh OS and
subsequent windowing based systems (NextStep, Microsoft
Windows, X-Windows, Motif, etc.).
73
Consider
No biological creature:
• Developed the wheel
• Flew to the moon
• Communications via radio
Much of engineering is not bio-inspired
74
Human level cognition
Seems to combine much of both worlds
• Symbol processing, reasoning,
exploration
• Use of tools
• Locomotion
• Adaptation, genetic variation,
reproduction
• Social structures (like ants, termites)
75
Popular Reading
• “John McCarthy: The uncommon logician of common
sense”, in Shasha & Lazere (1995).
• “Alan Kay: A clear romantic vision”, ibid.
• “Computers and Brains”, in Morowitz (1997).
Required Reading (at home)
• “Intelligence without reason” – Brooks (1991).
76
Some basics
• This module is for you. Think, read, ask questions,
tinker, and have fun!
• Warning: Some of the material covered is, or recently
was, cutting edge.
• There will be programming, some biology, some
philosophy.
• There is a lot of material to cover in lectures, but…
lecture slides will not tell the whole story. You must
attend lectures and demo sessions
• The module courseware – BEAST – will be introduced
over the coming weeks. Help with C++, installation etc.
will be given in demo sessions.
• Originality and innovation will be rewarded. Show
enthusiasm, play, contribute original code.
77
Assessment
•
•
•
•
2-Hour Exam (60%) - answer 3 questions of 4
2 assignments (40%) of which
1st assignment (15%)
will be announced shortly
2nd assignment includes BEAST analysis &
programming project. (25%) will be announced shortly.
• Additional exercises may be given in demo sessions.
• Assignments & exam must be passed to pass module.
78