Understanding what needs to be implemented

[jacques.d...@gmail.com]

Hi,

I am new to using julia-pomdp, and have been reading the documentation at http://juliapomdp.github.io/POMDPs.jl/latest/ and looking through examples in https://github.com/JuliaPOMDP/POMDPGallery.jl to try to get a sense of how this works.

I am a bit confused as to what needs to be implemented for different solvers to work. I was under the impression that the @requirements_macro would help me this. But when I try running some of the code in the POMDPGallery repo, I run into issues like the example I am giving below for Powseeker with the QMDPSolver. Is this because (i) with the current implementation of Powseeker.jl, QMDPSolver cannot be used, (ii) I am using the requirements macro incorrectly, (iii) I am completely misunderstanding the way the API works?

My understanding from reading the documentation was that if you implemented enough of either the generative or explicit functions, then POMDPs.jl would build the rest of the functions when necessary at runtime by inferring from what is implemented by the user. But I am now wondering whether I got this wrong and whether a different set of problem-defining functions needs to be implemented depending on the solver you are using. In that case, is there a shadow to the requirements macro that tells you what solvers can be used with a given problem implementation?

If it is easier for you to point me towards a section of the documentation that explains this, please do so!

I think my confusion may be linked to the statement at the beginning of the "Defining POMDPs" section in the documentation:

The expressive nature of POMDPs.jl gives problem writers the flexibility to write their problem in many forms. Custom POMDP problems are defined by implementing the functions specified by the POMDPs API.

This I understood to mean the problem can be written many different ways, so I thought the general workflow was to first think about the problem and how best to write it, and only think about solvers in a second step. In other words, that problem formulation/modeling was separate from problem resolution. Is the correct workflow to instead choose a solver (or set of solvers) and then write the problem such that it fits those solvers?

Thanks,

Jacques

               _

   _       _ _(_)_     |  A fresh approach to technical computing

  (_)     | (_) (_)    |  Documentation: https://docs.julialang.org

   _ _   _| |_  __ _   |  Type "?help" for help.

  | | | | | | |/ _` |  |

  | | |_| | | | (_| |  |  Version 0.6.0 (2017-06-19 13:05 UTC)

 _/ |\__'_|_|_|\__'_|  |  Official http://julialang.org/ release

|__/                   |  x86_64-apple-darwin13.4.0

julia> include("Powseeker.jl")

WARNING: deprecated syntax "typealias PowseekerProblem Union{PowseekerMDP,PowseekerPOMDP}" at /Users/jacquesdechalendar/Box Sync/Stanford Ed/AA228/project/gallery/Powseeker.jl/src/Powseeker.jl:94.

Use "const PowseekerProblem = Union{PowseekerMDP,PowseekerPOMDP}" instead.

Powseeker

julia> using Powseeker

julia> using POMDPToolbox

julia> using POMDPs

julia> using QMDP

julia> @requirements_info QMDPSolver() Powseeker

Powseeker      PowseekerMDP    PowseekerPOMDP

julia> @requirements_info QMDPSolver() PowseekerPOMDP()

INFO: POMDPs.jl requirements for solve(::QMDPSolver, ::POMDPs.POMDP) and dependencies. ([✔] = implemented correctly; [X] = missing)

For solve(::QMDPSolver, ::POMDPs.POMDP):

  [No additional requirements]

For solve(::ValueIterationSolver, ::Union{POMDPs.MDP,POMDPs.POMDP}) (in solve(::QMDPSolver, ::POMDPs.POMDP)):

  [✔] discount(::PowseekerPOMDP)

  [X] n_states(::PowseekerPOMDP)

  [X] n_actions(::PowseekerPOMDP)

  [X] transition(::PowseekerPOMDP, ::SkierState, ::GPSOrAngle)

  [X] reward(::PowseekerPOMDP, ::SkierState, ::GPSOrAngle, ::SkierState)

  [X] state_index(::PowseekerPOMDP, ::SkierState)

  [X] action_index(::PowseekerPOMDP, ::GPSOrAngle)

  [✔] actions(::PowseekerPOMDP, ::SkierState)

  WARNING: Some requirements may not be shown because a MethodError was thrown.

For ordered_states(::Union{POMDPs.MDP,POMDPs.POMDP}) (in solve(::ValueIterationSolver, ::Union{POMDPs.MDP,POMDPs.POMDP})):

  [X] states(::PowseekerPOMDP)

  WARNING: Some requirements may not be shown because a MethodError was thrown.

For ordered_actions(::Union{POMDPs.MDP,POMDPs.POMDP}) (in solve(::ValueIterationSolver, ::Union{POMDPs.MDP,POMDPs.POMDP})):

  [✔] actions(::PowseekerPOMDP)

  [X] iterator(::GPSOrAngleSpace)

Note: Missing methods are often due to incorrect importing. Consider using `importall POMDPs`.

Throwing the first exception (from processing solve(::ValueIterationSolver, ::Union{POMDPs.MDP,POMDPs.POMDP}) requirements):

ERROR: MethodError: no method matching states(::Powseeker.PowseekerPOMDP{Powseeker.#grad_scaled_peaks2})

Closest candidates are:

  states(::Union{POMDPs.MDP, POMDPs.POMDP}, ::Any) at /Users/jacquesdechalendar/.julia/v0.6/POMDPs/src/space.jl:26

  states(::POMDPs.MDP{Bool,A} where A) at /Users/jacquesdechalendar/.julia/v0.6/POMDPToolbox/src/convenience/implementations.jl:21

  states(::POMDPs.POMDP{Bool,A,O} where O where A) at /Users/jacquesdechalendar/.julia/v0.6/POMDPToolbox/src/convenience/implementations.jl:22

Stacktrace:

 [1] macro expansion at /Users/jacquesdechalendar/.julia/v0.6/DiscreteValueIteration/src/vanilla.jl:95 [inlined]

 [2] macro expansion at /Users/jacquesdechalendar/.julia/v0.6/POMDPs/src/requirements_internals.jl:51 [inlined]

 [3] get_requirements(::POMDPs.#solve, ::Tuple{DiscreteValueIteration.ValueIterationSolver,Powseeker.PowseekerPOMDP{Powseeker.#grad_scaled_peaks2}}) at /Users/jacquesdechalendar/.julia/v0.6/POMDPs/src/requirements_interface.jl:62

 [4] macro expansion at /Users/jacquesdechalendar/.julia/v0.6/QMDP/src/vanilla.jl:53 [inlined]

 [5] macro expansion at /Users/jacquesdechalendar/.julia/v0.6/POMDPs/src/requirements_internals.jl:51 [inlined]

 [6] get_requirements(::POMDPs.#solve, ::Tuple{QMDP.QMDPSolver,Powseeker.PowseekerPOMDP{Powseeker.#grad_scaled_peaks2}}) at /Users/jacquesdechalendar/.julia/v0.6/POMDPs/src/requirements_interface.jl:62

 [7] requirements_info(::QMDP.QMDPSolver, ::Powseeker.PowseekerPOMDP{Powseeker.#grad_scaled_peaks2}) at /Users/jacquesdechalendar/.julia/v0.6/POMDPs/src/requirements_interface.jl:140

julia> 

[Zachary Sunberg]

Hi Jacques,

Thanks for posting this well-posed question - it's helpful for us to understand where the documentation falls short.

There is a fundamental mathematical reason that the standard QMDP algorithm cannot solve Powseeker. Specifically, QMDP uses discrete value iteration on the fully observable MDP to approximate the alpha vectors. Since the Powseeker problem has a continuous state space, exact discrete value iteration cannot be used.

For the Powseeker problem, a generative model is easy to define, but an explicit model is difficult, thus, only solvers that use the generative interface* will work.

In that case, is there a shadow to the requirements macro that tells you what solvers can be used with a given problem implementation?

Not right now - that would be very useful and interesting, but not something I have time to tackle as a PhD student. 

I thought the general workflow was to first think about the problem and how best to write it, and only think about solvers in a second step. In other words, that problem formulation/modeling was separate from problem resolution. Is the correct workflow to instead choose a solver (or set of solvers) and then write the problem such that it fits those solvers?

Unfortunately this is not really the case in practice. Choosing a solver and writing the problem are highly coupled tasks. There are groups of solvers that have roughly the same requirements (e.g. POMCP and DESPOT both use basically the same generative functions), but the only way to exactly specify requirements is on a per-solver basis. This isn't because of how POMDPs.jl is implemented; it is due to the fundamental algorithmic differences in problem and solver structure. Implementing the explicit interface for simple discrete POMDPs will enable *all* POMDPs.jl solvers to work, but more complex problems must be tailored to the solver.

POMDPs.jl is not designed to remove the need for understanding the structure of POMDPs and the basics of how the solvers work**; instead, it is meant to give scientists and engineers the flexibility to use all the solvers

relevant to their problem with less effort than previous systems***.

Hope that helps!

- Zach

* Here I mean generative in a rough sense. For example, Powseeker can be used with POMCPOW, which requires ParticleFilters.obs_weight or POMDPs.observation in addition to generate functions.

** This is a much more difficult task, and I won't be able to tackle it in my PhD, but it seems like it would be possible to write a simplified interface on top of POMDPs.jl that would allow one express a subset of problems and use a subset of solvers with a simpler interface and less understanding.

*** e.g. http://bigbird.comp.nus.edu.sg/pmwiki/farm/appl/index.php?n=Main.HomePage

[jacques.d...@gmail.com]

Hi Zach,

Thank you for your quick answer. I am not done going through it, but as a quick reaction below is a reference to a paper by Warren Powell, a professor at Princeton. He is in a slightly different field than your group is (his usual applications are finance, transportation, and energy). He has done some work in recent years trying to clarify what he calls the "jungle of stochastic optimization". He has written longer papers on this, but I am linking a short version I think you may be interested in.

One of the key drivers for this work is that he tries to separate the design of a model from the design of policies. I think that is a worthwhile objective as I have myself long been confused by papers in which model and policy seemed impossible to separate, as though there was only one way of solving a given problem.

I understand that the Powseeker problem cannot be solved directly through QMDP, but I think it could be nice for the package to have an easy way of taking a continuous state MDP/POMDP and discretizing it automatically if you wanted to try QMDP (I have no idea whether this is at all feasible from an implementation perspective). Just a thought.

Thanks again for your answer,

Jacques

Powell, Warren B., and Stephan Meisel. "Tutorial on stochastic optimization in energy—Part I: Modeling and policies." IEEE Transactions on Power Systems 31.2 (2016): 1459-1467.

[Zachary Sunberg]

Hi Jacques,

Thanks for the article and suggestions. Indeed, providing a unified interface that can accommodate a wide range of problem, policy, and solver structures is a primary goal of POMDPs.jl. This discussion is definitely useful for me.

> I have myself long been confused by papers in which model and policy seemed impossible to separate, as though there was only one way of solving a given problem.

This is exactly the problem we are trying to mitigate. POMDPs.jl allows vastly different policies including ones based on alpha vectors (like Powell's "VFAs"), simple functions (like Powell's "PFAs"), and tree search (like Powell's lookahead policies).

To be clear, when I said "Choosing a solver and writing the problem are highly coupled tasks", I really meant *implementing* the problem. I think the actual workflow involves more steps:

1. Formulate the problem mathematically on paper as a POMDP. If you can formulate it as a POMDP, you can express it in POMDPs.jl and vice versa.

2. Investigate which solvers would be applicable to the problem (this should be done more by reading the literature than by using POMDPs.jl).

3. Implement the problem using POMDPs.jl in a way that matches the problem structure and satisfies the solver requirements.

A few facts might be worth stating just to be clear:

- The explicit interface and generative interface are not separate, but are in fact more hierarchical (this slide may (or may not) help clarify). If the explicit interface is implemented, the functions in the generative interface are automatically synthesized. The explicit interface just exposes more information to the solver.

- If properly used, POMDPs.jl *never* requires re-implementation; a single implementation can be used on *all applicable solvers*.

- Not all solvers are applicable for all problems.

We developed POMDPs.jl first to meet our research needs. Though we didn't consciously plan for this to happen, POMDPs.jl has turned into more of a MathProgBase type of interface, rather than a JuMP or Convex type of interface. We wish that it was like JuMP, but JuMP only focuses on convex and mixed-integer programming. This class of problems is both much easier to express and to solve than the class of POMDPs. Because POMDPs is such a broad class and because solvers must necessarily be approximate, there is tighter coupling between solver and problem implementation and problem- and solver- specific heuristics are very important.

We definitely would like POMDPs to be easier to understand, for the problem definitions to be more concise, and for the solvers to be more plug-and-play (e.g. QMDP should solve a discretized version of continuous problems as you suggest), but this is probably only possible for a subset of problems. Defining those subsets and implementing a higher-level JuMP-like interface (see https://github.com/JuliaPOMDP/POMDPs.jl/issues/149) is a difficult task, and unfortunately not related to my PhD, so I won't be able to work on it, but we would definitely love to have collaborators interface with us!

- Zach