Planning code ROS migration POMDP prediction planning (I)

One . Markov Ｍarkov Principle ：
First , The general meaning of Markov process is The future is only about the present , It has nothing to do with the past . The definition is as follows ：
$$F_{t_n,t_1,t_2\dots \dots t_{n-1}}\left(x_n\mid x_1,x_2\dots \dots x_{n}1\right)=F_{t_n{t}_{n-1}}\left(x_n\mid x_{n}1\right)$$
such “ The state of the next moment is related to the current state , It has nothing to do with the state of the last moment ” The nature of , It is called no aftereffect or Markov nature . The process with this property is called Markov process .
There are two important concepts in Markov process ： Transfer distribution function 、 Transfer probability

markov processes $X_t$ , Called conditional probability F s , t = P { X t ≤ y ∣ X s = x } F_{s, t}=P\left\{X_{t} \leq y \mid X_{s}=x\right\} Fs,t​=P{ Xt​≤y∣Xs​=x} Is the transfer distribution function of the process .
call $P\left(X_{t_n}=x_n\mid X_{t_n}=x_{n-1}\right)$ Is the transition probability .
Two . Partial Markov decision principle （POMDP）：
MDP Principle ： Online too much , Not here .
POMDP Principle ：
There are involved POMDP The paper of , Will explain its basic principle , such as ：
link : DESPOT: Online POMDP Planning with Regularization.

Pay attention to the following points ：
1. comparison MDP,POMDP Can't get $state$, Can only get $observation$;
2. By introducing $observation$, Added $observation$ be based on $state$ and $action$ The distribution of ;
3.$history$ Expressed as ：
h t = { a 1 , o 1 , … , a t , o t } h_{t}=\left\{a_{1}, o_{1}, \ldots, a_{t}, o_{t}\right\} ht​={ a1​,o1​,…,at​,ot​}
h t , a t + 1 = { a 1 , o 1 , … , a t , o t , a t + 1 } h_{t} ,a_{t+1}=\left\{a_{1}, o_{1}, \ldots, a_{t}, o_{t}, a_{t+1}\right\} ht​,at+1​={ a1​,o1​,…,at​,ot​,at+1​}
And is defined as $action$ and $observation$ Of sequence;
4.$belief$ Is defined as $state$ be based on $history$ The distribution of ;

Detailed basic explanation :POMDP Basics .
3、 ... and . Use despot To solve the POMDP The overall framework ：
1. Input b（ Confidence space ）, adopt buliddespot The model gets l(lowerbound)
2. Find the biggest l Of a( action )
3. If the strategy of confidence space gets more reward than the one chosen a Big , Use at this time b The original strategy chooses a
4. Executive action a
5. Accept observation and measurement z
6. According to the observation , action , And the current state , Get the state of the next moment

among ,builddespot Framework ：
1. from K Get a series of
2. Build a new one despot Model , Take a new point as the root node
3. initialization U,L,l,u
4. obtain e(b0)=u(b0)-l(b0)
5. When e(b0)>e, And the running time is less than the maximum running time ：
6.b=EXPLORE(D,b)
7.BACKUP(D,b)
8.e(b0)=u(b0)-l(b0)
return l