Optimal Ordered Problem SolverTR IDSIA-12-02; arXiv:cs.AI/0207097, July 2002 (also NIPS 2002)

Non-Incremental Universal Search for problems with quickly verifiable solutions (Levin 1973)

Non-Incremental Osearch

PPT Slide

Incremental Optimal Search?

Bias-Optimality

Example from AI Planning

Incremental search: Update probability distribution by experience?

Optimal Ordered Problem Solver (OOPS):Get rid of the constants! (Schmidhuber, 2002)

Programs are composed from primitives

OOPS: Two near-bias-optimal searches

Implementation: FORTH-like language(many other languages / primitives are possible)

Experiment 2: Towers of Hanoi

Experiment 1: context free language 1n2n

Towers of Hanoi: incremental solutions

Analysis of Hanoi solver

Physical Limitations of OOPS

Disclaimer: OOPS has nothing to do with Genetic Programming etc

Ongoing: OOPS for learning robots

Email: juergen@idsia.ch

Home Page: http://www.idsia.ch/~juergen