How can we design a more intelligent path-planning?

Akira Imada

Brest State Technical University (Belarus)

(KoDi-2009) 2

Is AI really intelligent?

They might be more efficient and/or effective than human but still less intelligent, at least so far.

(KoDi-2009) 3

What is intelligence?

⇓

Intelligence should be spontaneous, flexible, and/or unpredictable, more or less.

(KoDi-2009) 4

“I beg your pardon?”

Intelligent people try a different explanation for an easier understanding

while

others just repeat the same expression, maybe with a louder voice.

(KoDi-2009) 5

Let’s make an agent to be spontaneous!

Behaviors might differ even in a similar situations.

(KoDi-2009) 6

Goal is

to make an agent behave differently even when it encounters the same situation as before.

(KoDi-2009) 7

Path Planning as a benchmark

An agent plans a shortest path from start to goal.

(KoDi-2009) 8

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 ...) indicates the agent a route to be followed.

(KoDi-2009) 9

Random walk evolved to be minimized

(KoDi-2009) 10

Task was easy

(KoDi-2009) 11

(An interpretation of GA from robotics point of view)

Edelman’s Neural Darwinism (1978)

Assume evolution in an agent’s brain in advance the action.

(e.g. 100 random chromosomes to be evolved)

⇓ after a convergence

⇓

Agent acts following the best chromosome.

(KoDi-2009) 12

Route can be different from run to run, if any.

(KoDi-2009) 13

It’s not so realistic, however.

No one, these days, believe this really happens. It takes a too long time to be a reality if the task is hard.

⇓ Let’s dismiss GA now.

(KoDi-2009) 14

What about NN?

With fixed weights

⇓

An identical behavior in an identical situation.

What if we modify weights during action? (Floreano et al. 2000)

(1)

Recurrent McCullough-Pitts Neurons with Sigmoid

Learning Rule

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

Optimum configuration of learning rules.

η_{ij}x_{i}y_{j} (Hebb, 1949)

or

a_{ij}x_{i}y_{j} + b_{ij}x_{i} + c_{ij}y_{j} + d (Durr et al. 2008)

(KoDi-2009) 18

Can agents take a different minimum route every time following how it feels?

(KoDi-2009) 19

(2)

Recurrent Spiking Neurons as a more biologically plausible model.

(KoDi-2009) 20

An exploration by Integrate & Fire Model

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

Can it learn so that path will finish at the goal with minimum length?

(KoDi-2009) 21

Spike timing dependent plasticity

(STDP)

A counterpart of Hebb Rule of McCullough-Pitts Neurons for Spiking Neurons.

(KoDi-2009) 22

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)

(KoDi-2009) 23

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)

(KoDi-2009) 24

Looks like a simple toy problem?

No!

(KoDi-2009) 25

More challenging benchmark

From one point to the same point maximizing its route with a limited fuel.

Brief Summary

We sometimes need spontaneous and unpredictable intelligence rather than efficiency or effectiveness like in case of SONY’s AIBO

(KoDi-2009) 27

Robot dog vs. Real dog

When will a robot dog be more intelligent than real dogs?