Spike timing dependent plasticity

(STDP)

to make robot navigation intelligent

Akira Imada Brest State Technical University (Belarus)

This is not a success report

but

a guideline of our ongoing project

or

a report of what we are currently planning.

To start with a benchmark to know

if what we are planning will work or not.

(Seminar in the Institute of Mathematics and Informatics, Vilnius) 4

Benchmark will be

Path Planning

or

Robot Navigation

⇓ where

the aim is usually to minimize the route from start to goal, but...

Task of minimizing navigation on its own is not so difficult

⇓

A-star, Genetic Algorithm, Reinforcement Learning, Neural Network, Ant Colony Optimization, etc...

Genetic Algorithm (GA)

⇓

Agent decides actions following its chromosome

e.g. with chromosomes like

(4 1 1 2 1 3 2 3 3 4 2 1 3 4 3 2 3 3 2 1 1 3 2 1 3 ...)

(Seminar in the Institute of Mathematics and Informatics, Vilnius) 7

Random walk evolved to be minimized

(Seminar in the Institute of Mathematics and Informatics, Vilnius) 8

Task was easy

(Seminar in the Institute of Mathematics and Informatics, Vilnius) 9

Let’s extend it

From Minimization to Maximization

⇓ i.e.

We don’t care goal points but to maximize an exploration

A Camel in a Desert

The 52nd problem

in the

“Propositiones ad acuendos inventes” (in Latin)

by

Alcuin of York (732–804)

(Seminar in the Institute of Mathematics and Informatics, Vilnius) 11

Can a camel maximize its exploration in a desert surviving with grains on his back?

(Seminar in the Institute of Mathematics and Informatics, Vilnius) 12

Modern version: From Camel to Jeep in a Desert

(Seminar in the Institute of Mathematics and Informatics, Vilnius) 13

Can a jeep maximize its exploration in a desert with a tank of fuel?

(Seminar in the Institute of Mathematics and Informatics, Vilnius) 14

Still it’s not so difficult by GA for example Task was rather easier

The complexity is O(N)

(Seminar in the Institute of Mathematics and Informatics, Vilnius) 16

Why not extend it further

Let’s make it return to the point it started ⇓

while also maximizing an exploration

(Seminar in the Institute of Mathematics and Informatics, Vilnius) 17

Planet Land-rover Problem

From A (start) to B (goal) minimizing its route

⇓

From A to A maximizing its route (This is our proposal here as a benchmark)

(Seminar in the Institute of Mathematics and Informatics, Vilnius) 18

Can the rover return to the base with its exploration being maximum

spending a limited energy given when it started?

Much more demanding

⇓

Taking GA as an example, what might be a fitness?

e.g.

{total length} & {how often it has crossed previous route?} with

Multi Objective GA (MOGA)

A Heuristic create such a route

What heuristic do you guess?

(Seminar in the Institute of Mathematics and Informatics, Vilnius) 21

Topic of today’s talk:

What is intelligence?

⇓

Intelligence should be spontaneous, flexible, or unpredictable more or less

(Seminar in the Institute of Mathematics and Informatics, Vilnius) 22

Stolle et al. (2002)

“... every day we might be cooking a different breakfast, but the kitchen layout is the same from day to day.”

(Seminar in the Institute of Mathematics and Informatics, Vilnius) 23

“I beg your pardon?”

Intelligent people try a different explanation for an easier understanding

while others repeat the expression, maybe with a bigger voice

(Seminar in the Institute of Mathematics and Informatics, Vilnius) 24

What if your canary stop singing?

Legendary three strategies in Japan.

(1) Just wait until she sings again.

(2) Try something so that she sings again.

(3) Kill her if she doesn’t sing any more?

To be intelligent,

action should be different more or less even in an exactly identical situation

(Seminar in the Institute of Mathematics and Informatics, Vilnius) 26

Performance is not intelligent

if we use deterministic A-star, GA, NN with fixed weights?

(Seminar in the Institute of Mathematics and Informatics, Vilnius) 27

Let’s make a learning occur during behaviors ⇓

Evolution of Learning

A notation

Hebbian Learning of NN

w_{ij}(t + 1) = w_{ij}(t) + ηx_{j}(t)y_{i}(t) (x_{j}, y_{i} ∈ [0, 1])

(Seminar in the Institute of Mathematics and Informatics, Vilnius) 29

Floreano’s approach (2000)

⇓

Modification of w_{ij} during exploration with either one of four Hebbian and Hebbian-like rules

(Seminar in the Institute of Mathematics and Informatics, Vilnius) 30

Hebbian learning

(1) Δw = (1 − w)xy

(Seminar in the Institute of Mathematics and Informatics, Vilnius) 31

Hebbian type learning

Weaken if the post-synaptic is active, while the pre-synaptic is not

(2) Δw = w(−1 + x)y + (1 − w)xy

Weaken if the pre-synaptic is active, while the post-synaptic is not (3) Δw = wx(−1 + y) + (1 − w)xy

(Seminar in the Institute of Mathematics and Informatics, Vilnius) 32

And

Strengthen if the two have similar activity and weaken otherwise.

(4) Δw = \{ \begin{matrix}(1 − w)F (x, y) & if F (x, y) > 0 \\ wF (x, y) & otherwise \end{matrix}

where F (x, y) = tanh(4(1 − |x − y|) − 2)

(Seminar in the Institute of Mathematics and Informatics, Vilnius) 33

Evolution of leaning

Which rule and what parameter’s value should be assigned

to each of the synapses? ⇓ Evolution leads the combination to the optimum.

(Seminar in the Institute of Mathematics and Informatics, Vilnius) 34

Stanley’s implementation (2003)

Δw = \{ \begin{matrix}η_{1}(1 − w)xy + η_{2}wx(y − 1) & for excitatory neuron \\ −η_{1}(1 − w)xy + η_{2}(1 − w)x(1 − y) & for inhibitory neuron \end{matrix}

⇓

Evolution is on (η_{1}, η_{2}) of each synaptic weight

(Seminar in the Institute of Mathematics and Informatics, Vilnius) 35

Their result

Starting with random weights every time anew the weights are modified step by step by the rule it learned

⇓

Every run is different depending on the initial random weights

(Seminar in the Institute of Mathematics and Informatics, Vilnius) 36

More general learning (Durr et al. 2008)

Δw = η(Axy + Bx + Cy + D)

An example of exploration by a recurrent NN with random weights

Can it learn so that path will finish at the start point?

(Seminar in the Institute of Mathematics and Informatics, Vilnius) 38

Our Aim ⇓

Learning should occur during a random exploration with a spiking neural network to seek its biological plausibility

(Seminar in the Institute of Mathematics and Informatics, Vilnius) 39

Learning by STDP

(Spiking neuron’s version of Hebbian Learning)

⇓

The topic is still open!

(Seminar in the Institute of Mathematics and Informatics, Vilnius) 40

Meunier et al. (2005) ⇓

“Up to now, nobody has been able to show how it is possible to learn with STDP...”

Farries et al. (2007)

⇓

“Although synaptic plasticity is widely believed to be a major component of learning, it is unclear how STDP itself could serve as a

mechanism for general purpose learning.”

Still the method is not so fruitful

but

Why not challenge?

Architecture we are planning

⇓ a.k.a.

Echo State Network, Liquid State Network or Reservoir Computing

(Seminar in the Institute of Mathematics and Informatics, Vilnius) 44

Integrate-and-Fire Model

u_{i}(t) = u_{r} + (u_{i}(t − δt) − u_{r}) exp(−δt/τ) + ∑_{j} w_{ij}f_{j}(t − δt)

(Seminar in the Institute of Mathematics and Informatics, Vilnius) 45

What is STDP?

W (Δt) = \{ \begin{matrix}A_{+} exp(−Δt/τ_{+}) & if Δt ≥ 0 \\ −A_{−} exp(−Δt/τ_{−}) & if Δt < 0 \end{matrix}

where Δt = t_{post} − t_{pre}

W (Δt)

(Seminar in the Institute of Mathematics and Informatics, Vilnius) 46

In short

potentiation occurs when a pre-synaptic neuron fires

shortly before a post-synaptic neuron

and

depression occurs when the post-synaptic neuron fires shortly after.

(Seminar in the Institute of Mathematics and Informatics, Vilnius) 47

It’s too basic to be applied to a real simulation

(Seminar in the Institute of Mathematics and Informatics, Vilnius) 48

Reward-modulated STDP Learning

(Florian 2007)

w_{ij}(t + δt) = w_{ij}(t) + γr(t + δt)ζ_{ij}(t)

where

ζ_{ij}(t) = P_{ij}^{+}(t)f_{i}(t) + P_{ij}^{−}(t)f_{i}(t) P_{ij}^{+}(t) = P_{ij}^{+}(t − δt) exp(−δt/τ_{+}) + A_{+}f_{j}(t) P_{ij}^{−}(t) = P_{ij}^{−}(t − δt) exp(−δt/τ_{−}) + A_{−}f_{j}(t)

Reinforcement Learning (RL)

What an agent learns is a policy

and

policy is how to select an action in a given situation (state)

maximizing

total rewards the agent occasionary will receive from the environment

(Seminar in the Institute of Mathematics and Informatics, Vilnius) 50

Policy indicates agent which action should be chosen

in any possible situation

⇓ While in GA

Agent decides actions following its chromosome

in RL

Agent decides actions following its policy it has already learned

(Seminar in the Institute of Mathematics and Informatics, Vilnius) 51

However

our world is with no obstacle, no wall, no corridor, only one goal

⇓

Everywhere no reward except for one point (goal)

⇓

A needle in a Haystack

(Rewards are not likely to be encountered by a random exploration)

(Seminar in the Institute of Mathematics and Informatics, Vilnius) 52

We have not succeeded yet

Nevertheless

we think of

a further extention of the benchmark

as a bigger challenge

⇓

What if the rover carries containers for fuel?

(Seminar in the Institute of Mathematics and Informatics, Vilnius) 53

Jeep Problem

Where jeep explore is 1-D desert Jeep can unload its fuels anywhere in the desert

Fuels can be filled only at the base Jeep can go back to the base n times to re-fill its tank

⇓ thus

The jeep should maximize its penetration

(Seminar in the Institute of Mathematics and Informatics, Vilnius) 54

An example of a success

(Seminar in the Institute of Mathematics and Informatics, Vilnius) 55

Let’s give the rover the same condition

⇓

A very tough benchmark, and

an infinitely large number of solutions (when it’s in 2-D)

⇓

Good as a benchmark to check our intelligence of a differenct action in a same environment

(Seminar in the Institute of Mathematics and Informatics, Vilnius) 56

Let me conclude

To claim artificial NN to be intelligent

a different action more or less should be made under identical situation.

⇓

We want to, or we are going to realize it

by

Spiking NN with learning by STDP

also

to be more biologically plausible.

SONY’s AIBO

can excellently learn but still repeats same action in the same situation

Hoping collaborations

to design

an agent like real human intelligence

Thank You!