Can a learning robot survive in a desert? A 2-D expansion of the jeep problem

Akira Imada Brest State Technical University Belarus

(ACS-2007 – at Miedzyzdroje, Poland) 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 unique x fulfills F (x) = 1 while F (x) = 0 for all others.

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

(ACS-2007 – at Miedzyzdroje, Poland) 5

Complexity of the search

⇓ Linear or

We need O(N) steps to reach the needle!

(ACS-2007 – at Miedzyzdroje, Poland) 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.

E.g. (00110 10101 11010 10101)

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

Their choice of 20-bit was a good one!

Therefore, their experiment was not a very difficult one. But can we reach a needle longer than 25 bits?

How we evolve all-fitness-0 chromosomes?

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

(ACS-2007 – at Miedzyzdroje, Poland) 10

Hinton & Nowlan’s brilliant trick

Evolution under Baldwin effect

— Lifetime learning of phenotype

A genotype:

(10901099011001001091)

Its phenotype: (10101001011001001001) (10001011011001001011)

...

(ACS-2007 – at Miedzyzdroje, Poland) 11

Baldwin effect ⇓ A hypothesis for biological evolution

Abilities obtained in parent’s lifetime will inherit to offspring

(ACS-2007 – at Miedzyzdroje, Poland) 12

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.

(ACS-2007 – at Miedzyzdroje, Poland) 13

Baldwin effect looks great!

(ACS-2007 – at Miedzyzdroje, Poland) 14

I’m not an evangelist!

(ACS-2007 – at Miedzyzdroje, Poland) 15

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

(ACS-2007 – at Miedzyzdroje, Poland) 16

Still we are not so happy.

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

(ACS-2007 – at Miedzyzdroje, Poland) 17

Effect of

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

⇓

An intelligent strategy is sometimes worse than a random one!

A needle in a grid world

No landmarks like walls, corridors, or obstacles.

⇓

How can we know “Where we are?” or “Where to go?”

(ACS-2007 – at Miedzyzdroje, Poland) 19

A random walk to the needle

(ACS-2007 – at Miedzyzdroje, Poland) 20

Random walk evolved to be minimized

(ACS-2007 – at Miedzyzdroje, Poland) 21

Evolution successful

(ACS-2007 – at Miedzyzdroje, Poland) 22

Number of steps grows linearly

(ACS-2007 – at Miedzyzdroje, Poland) 23

What if the grid is huge?

It seems less likely to reach the needle by chance.

(ACS-2007 – at Miedzyzdroje, Poland) 24

Evolution will be harder as grid becomes larger

(ACS-2007 – at Miedzyzdroje, Poland) 25

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.

(ACS-2007 – at Miedzyzdroje, Poland) 27

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.

(ACS-2007 – at Miedzyzdroje, Poland) 28

A Stupid one but anyhow ...

(ACS-2007 – at Miedzyzdroje, Poland) 29

An example of a success for n=3

(ACS-2007 – at Miedzyzdroje, Poland) 30

An analytical optimal solution

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

(ACS-2007 – at Miedzyzdroje, Poland) 31

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

Przemysław Klȩsk (2004)

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

(ACS-2007 – at Miedzyzdroje, Poland) 33

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

(ACS-2007 – at Miedzyzdroje, Poland) 34

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.

(ACS-2007 – at Miedzyzdroje, Poland) 35

Examples of a possible trace

What we challenge here

• In a 2-D desert

⋆ For n = 1

- This is simply a-needle-search ⋆ For n ≥ 2

- Maximize penetration

- Search for a hidden needle • In a higher dimensional grid

Still resists to be solved!

Evolutionary Computation

...... Reinforcement learning

⇓

An extremely tough benchmark A challenge to a navigation robot community.

(ACS-2007 – at Miedzyzdroje, Poland) 38

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

(ACS-2007 – at Miedzyzdroje, Poland) 39

A strange path of quantum computation

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

(ACS-2007 – at Miedzyzdroje, Poland) 40

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 because we tend-to-hear-what-we-want-to-hear.

• Success report sometimes holds true only in a small world.