stateindex for MDP without CartesianIndices

[ThomasDeMunck12]

Hello,

I am currently struggling with the function stateindex at the moment of solving a simple MDP with value iteration.

Basically, my problem is the following:
I have taxis traveling around locations to serve riders. There can be a maximum of n_cars in the network. Thus, the state is described by two vectors. One for the number of cars in each node (I have two transit and two pick-up nodes) and one for the number of riders waiting in each location (max_wait is the max number of riders waiting).

I define:

function POMDPs.states(mdp::RideHailingEnv)
    s = RideHailingState[] # initialize an array of RideHailingStates

    #loop over all our states
    for i = 0:mdp.n_cars, j = 0:mdp.n_cars, k = 0:mdp.n_cars, l = 0:mdp.n_cars, m = 0:mdp.max_wait, n = 0:mdp.max_wait

        if i+j+k+l==mdp.n_cars
            push!(s, RideHailingState([i,j,k,l],[m,n]))
        end
    end
    return s
end;

At the moment of indexing my states, I do not exactly know how to do it efficiently. Using a typical function as CartesianIndices would not work as the number of states would be way too large.

For instance, state index would create me n_cars^4*max_wait^2 possible indexes while I only need factorial(n_cars+n_locations-1)/factorial(n_locations-1)*(n_cars) indexes. Another example: if I have 5 cars, RideHailingState([3,1,2,0],[1,0]) would be indexed with CartesianIndices while actually not valid

I am not particularly an expert in programming. Therefore, I was wondering if there would exist a way to index the states efficiently for the problem I just described.

Thanks in advance for the reply!

[zsunberg]

Hi @dmteams , Thanks for your question - I hope we can assist. I hope you don't mind that I converted this to a discussion.

One quick and dirty way to do it is to store a dictionary in the RideHailingEnv object (the downside is it might take a while to construct an object in this case)

struct RideHailingEnv
    s_inds::Dict{RideHailingState, Int}
    # ...
end

function fill_state_inds!(m::RideHailingEnv)
    for (i, s) enumerate(states(m))
        m.s_inds[s] = i
    end
end

POMDPs.stateindex(m::RideHailingEnv, s::RideHailingState) = m.s_inds[s]

Which solver(s) are you planning to use? You may not need to define the stateindex function at all.

[ThomasDeMunck12]

Hello,

Thank you a lot for the reply!

I was planning to solve it first w/ the SparseValueIterationSolver. Then, move progressively towards more RL-related techniques as I increase the complexity of the problem. I can imagine that in this case, I won't need to have stateindex defined anymore.

Anyway, what you proposed is indeed one easy and relevant way to do it, which is working in my case. :)