Can a learning robot solve a 2-D jeep problem?

Akira Imada Brest State Technical University

Belarus

(AMiRE-2007 – at Buenos Aires, Argentina) 2

Looking for “a-needle-in-a-haystack”

A needle hidden in a huge grid world

Can a navigation robot reach it?

⇓

A 2-D version of a-needle-in-a-haystack.

What is a-needle-in-a-haystack

“Find x (among N items) such that F (x) = 1”

when

only x fulfills F (x) = 1 while F (x) = 0 for all others.

(We might call F (x) a fitness function of this problem.)

(AMiRE-2007 – at Buenos Aires, Argentina) 5

O(N) steps are necessary!

(AMiRE-2007 – at Buenos Aires, Argentina) 6

How we search the needle as efficiently as possible?

⇓

More efficient than a Random/Exhaustive search?

Hinton & Nowlan’s Needle (1987)

• A-needle ⇒ Just one configuration of 20-bit binary strings.

• Haystack ⇒ 2^{20} − 1 search points.

Their choice of 20-bit was a good one!

Hence, their experiment was not a very difficult one.

How we evolve all-fitness-0 chromosomes?

• What about the task called “All-one-problem?” (9 × 14 ⇒ 16 ⇒ 17 vs. 0 × 0 ⇒ 0 ⇒ 0)

(AMiRE-2007 – at Buenos Aires, Argentina) 10

Hinton & Nowlan’s brilliant trick

Evolution under Baldwin effect

— Lifetime learning of phenotype

A genotype:

(10901099011001001091)

Its phenotype: (10101001011001001001) (10001011011001001011)

...

(AMiRE-2007 – at Buenos Aires, Argentina) 11

Their assumption

The closer the genotype to the needle,

the faster the learning of phenotype.

⇓

This makes the sharp-fitness-peak a more smooth one.

(AMiRE-2007 – at Buenos Aires, Argentina) 12

Baldwin effect looks great!

(AMiRE-2007 – at Buenos Aires, Argentina) 13

Are we really happy with this?

Why should we continue evolution when lifetime-learning already has found the needle?

⇓ (Turney 1987)

“Not from an engineering but a biological interest.”

(AMiRE-2007 – at Buenos Aires, Argentina) 14

Still we are not so happy.

The number of individuals, or the number of total points visited?

(AMiRE-2007 – at Buenos Aires, Argentina) 15

Effect of

like-to-hear-what-we’d-like-to-hear?

⇓

An intelligent strategy is sometimes worse than a random one!

(AMiRE-2007 – at Buenos Aires, Argentina) 16

A random walk to the needle

(AMiRE-2007 – at Buenos Aires, Argentina) 17

Random walk evolved to be minimized

(AMiRE-2007 – at Buenos Aires, Argentina) 18

Evolution successful

(AMiRE-2007 – at Buenos Aires, Argentina) 19

Number of steps grows linearly

(AMiRE-2007 – at Buenos Aires, Argentina) 20

What if the grid is huge?

It seems less likely to reach the needle by chance.

(AMiRE-2007 – at Buenos Aires, Argentina) 21

Evolution will be harder as grid becomes larger

(AMiRE-2007 – at Buenos Aires, Argentina) 22

A success at a small scale is not a royal road to a real success.

The Jeep Problem

The 52nd problem

in the

“Propositiones ad acuendos inventes” (in Latin)

attributed to

Alcuin of York (732–804)

⇓

Camel carrying grain in a desert.

(AMiRE-2007 – at Buenos Aires, Argentina) 24

The task in the modern version

Maximize the distance a Jeep can penetrate into 1-D desert.

• Jeep can move a unit distance with a unit fuel.

• 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.

(AMiRE-2007 – at Buenos Aires, Argentina) 25

An example of a success

(AMiRE-2007 – at Buenos Aires, Argentina) 26

An analytical solution

by N. J. Fine (1947) d_{0} = 0, d_{n} = d_{n−1} + 1/(2n − 1).

(AMiRE-2007 – at Buenos Aires, Argentina) 27

The optimum solution for n=3 A solution by a GA

Przemysław Klȩsk (2004)

Conluded, “Solution for n > 3 was not available!!

(AMiRE-2007 – at Buenos Aires, Argentina) 29

An extension to 2-D Desert

“Maximize the penetration” or “Find the needle” by repeating the procedure:

(1) Start the base.

(2) Navigate the desert.

(3) Put fuels somewhere, or find the fuels to get.

(4) Return to the base.

(AMiRE-2007 – at Buenos Aires, Argentina) 30

Examples of a possible trace Still resists to be solved!

Evolutionary Computation

...... Reinforcement learning

etc ⇓

An extremely tough benchmark

(AMiRE-2007 – at Buenos Aires, Argentina) 32

Grover’s quantum search (1997) A speed up from O(N) to O(\sqrt{N}).

(AMiRE-2007 – at Buenos Aires, Argentina) 33

A strange path of quantum computation

When a particle goes from A to B, it takes all possible paths at the same time.

(AMiRE-2007 – at Buenos Aires, Argentina) 34

Quantum Robot

Paul Benioff (2002)

⇓

“Only faster than classical search in more than 2-D!”

Summary

• Two challenges:

⋆ A needle hidden in a huge grid world.

⋆ 2-D Jeep Problem by a learning navigation robot.

Can a robot learn to solve this? Then how, if any?

• We have to be careful about an effect of tend-to-hear-what-we-want-to-hear.

• Success at a small scale is not a success in a real world.