FiniteHorizonPOMDPs.jl

[Omastto1]

Hi,
I have implemented a concept version of FiniteHorizonPOMDPs.jl and created 10 tiles GridWorld (as proposed by @zsunberg) to show the idea of a possible solution.

The package consists of a simple epoch solver that currently works with the MDP version of DiscreteValueIteration Solver and a structure that stores its results.

Repository is here.

Example instance is tested as equality comparison of the result of value iteration solver against proposed finite horizon interface.
As I did not find a straight forward solution to implement MDP to FiniteHorizonMDP wrapper I created two problem definitions. One for value iteration and one for the finite horizon. Those are stored in /test/instances/...

I think that the mentioned wrapper would make the problem implementation much easier (and it is also proposed in JuliaPOMDP/FiniteHorizonPODMP.jl's readme file).
Also, the method works only with ValueIteration so far. I will be glad for more solver recommendations
I will be happy for any feedback from the community as to which direction should I head with implementation.
Tom

[zsunberg]

Hey Tom,

Very cool! It looks like a great start! I think you got the main concepts right.

I will have a lot of feedback, but will start with the following things:

1. I think the goal should be to have a single problem definition that can be solved both by the DiscreteValueIteration.jl solvers, but also (faster) by your specialized finite horizon solver. So the instances folder should just have the 1DFiniteHorizonGridWorld example, and I would like to see the following test:

   m = 1DFiniteHorizonGridWorld()
   mypolicy = mysolve(m)
   vipolicy = solve(DiscreteValueIteration.ValueIterationSolver(), m)
   @test all(action(mypolicy, s) == action(vipolicy, s) for s in states(m))

   If it passes this test, you should be able to use all POMDPs.jl solvers. To implement this, the relationship between stage_states and POMDPs.states should be something like

   POMDPs.states(m) = Iterators.flatten(stage_states(m, i) for i in stages(m))

2. Instead of using the value iteration solver from DiscreteValueIteration.jl, I think you should write your own value iteration loop. The current code in DiscreteValueIteration.jl is really verbose, so don't copy that (PRs to make that nicer are MUCH appreciated by the way :)). Your inner loop will look something like this for example:

   next_stage_value = maximum(stage_q; dims=2)
   stage_q = fill(-Inf, #=appropriate size=#)
   for s in stage_states(m, stage)
       for a in actions(m, s)
           si = stage_state_index(m, stage, s)
           ai = action_index(m, a)
           for (sp, p) in weighted_iterator(transition(m, s, a))
               spi = stage_state_index(m, sp)
               stage_q[si, ai] += reward(m, s, a, sp) + discount(m)*maximum(next_stage_value[spi])
           end
       end
   end

   It would probably be even faster to construct sparse transition matrices for each stage, and do the value iteration with those.
3. Conceptual note: I am envisioning two separate ways to create fixed horizon (PO)MDPs: (1) fixhorizon wraps any existing infinite-horizon POMDP so that it becomes a POMDP and (2) you can create one yourself as described above.

Let me know if that all makes sense. It would also be possible to have a short zoom meeting if you have complicated questions that are difficult to write out.

Good luck! I think this will be really nice when finished.

[zsunberg]

Ok, great! Looks like a lot of good changes. Do you want to move forward with making this a registered package? (there will be a lot of changes that I will recommend :) )

[zsunberg]

There are a lot of comments I would like to make on individual lines, but I'm not sure if there is a way to do that currently. If you want to make a pull request to JuliaPOMDP/FiniteHorizonPOMDPs.jl, that might be easiest.

[Omastto1]

Ok,
I have a few improvement ideas as well.
I also did a pull request.
Initially, I made my own repo instead of a fork. I hope I fixed it, as it looks like the commits did copy.
My issues stayed on the original repo.

[zsunberg]

Cool! Thanks for the PR. I will probably get some time to look at it Monday or Tuesday.

[zsunberg]

Hi @Omastto1 , sorry for such a long delay. I have left my review here: JuliaPOMDP/FiniteHorizonPOMDPs.jl#3 (review). Will try to give shorter responses but more quickly going forward.