Constructing skill trees
CST consists of mainly three parts;change point detection, alignment and merging. The main focus of CST is online change-point detection. The change-point detection algorithm is used to segment data into skills and uses the sum of discounted reward formula_1 as the target regression variable. Each skill is assigned an appropriate abstraction. A particle filter is used to control the computational complexity of CST. The change point detection algorithm is implemented as follows. The data for times formula_2 and models Q with prior formula_3 are given. The algorithm is assumed to be able to fit a segment from time formula_4 to formula_5 using model formula_6 with the fit probability formula_7. A linear regression model with Gaussian noise is used to compute formula_7. The Gaussian noise prior has mean zero, and variance which follows formula_9. The prior for each weight follows formula_10. The fit probability formula_7 is computed by the following equation. formula_12
Then, CST compute the probability of the changepoint at time j with model q, formula_13 and formula_14 using a Viterbi algorithm. formula_15
formula_16
The descriptions of the parameters and variables are as follows;
formula_17
formula_18: a vector of m basis functions evaluated at state formula_19
formula_20
formula_21
formula_22
formula_23: Gamma function
formula_24
formula_25: The number of basis functions q has. formula_26: an m by m matrix with formula_27 on the diagonal and zeros else where
The skill length formula_28 is assumed to follow a Geometric distribution with parameter p
formula_29
formula_30
formula_31
formula_32Expected skill length
Using the method above, CST can segment data into a skill chain. The time complexity of the change point detection is formula_33 and storage size is formula_34, where formula_35 is the number of particles, formula_36 is the time of computing formula_37, and there are formula_38 change points. Next step is alignment. CST needs to align the component skills because the change-point does not occur in the exactly same places. Thus, when segmenting second trajectory after segmenting the first trajectory, it has a bias on the location of change point in the second trajectory. This bias follows a mixture of gaussians. The last step is merging. CST merges skill chains into a skill tree. CST merges a pair of trajectory segments by allocating the same skill. All trajectories have the same goal and it merges two chains by starting at their final segments. If two segments are statistically similar, it merges them. This procedure is repeated until it fails to merge a pair of skill segments. formula_39 are used to determine whether a pair of trajectories are modeled better as one skill or as two different skills. The following pseudocode describes the change point detection algorithm:
 particles := [];
 Process each incoming data point
 for t = 1:T do
 //Compute fit probabilities for all particles 
 for formula_40 do
 p_tjq := (1 − G(t − p.pos − 1)) × p.fit_prob × model_prior(p.model) × p.prev_MAP 
 p.MAP := p_tjq × g(t−p.pos) / (1 − G(t − p.pos − 1))
 end
 "// Filter if necessary"
 if the number of particles ≥ N then
 particles := particle_filter(p. MAP, M)
 end
 "// Determine the Viterbi path"
 for t = 1 do
 max_path := []
 max_MAP := 1/|Q|
 else
 max_particle := formula_41p. MAP
 max_path := max_particle.path formula_42 max_particle
 max_MAP := max_particle. MAP
 end
 "// Create new particles for a changepoint at time t"
 for formula_43 do
 new_p := create_particle(model=q, pos=t, prev_MAP=max_MAP, path=max_path)
 p := p formula_44 new_p
 end
 "// Update all particles"
 for formula_45 do
 particles := update_particle(current_state, current_reward, p) 
 end
 end
 "// Return the most likely path to the final point"
 return max_path
 function update_particle(current_state, current_reward, particle) is
 p := particle
 r_t := current_reward
 "// Initialization"
 if t = 0 then
 p.A := zero matrix(p.m, p.m)
 p.b := zero vector(p.m)
 p.z := zero vector(p.m)
 p.sum r := 0
 p.tr1 := 0
 p.tr2 := 0
 end if
 "// Compute the basis function vector for the current state"
 formula_46 := p.formula_47(current state)
 "// Update sufficient statistics"
 p.A := p.A+formula_48
 p.z := formula_49p.z+formula_50 p.b := p.b+formula_51 p.z
 p.tr1 := 1+ formula_52 p.tr1
 p.sum r := sum p.r+ formula_53 p.tr1+2formula_54 p.tr2
 p.tr2 := formula_49p.tr2+formula_51 p.tr1
 p.fit_prob := compute_fit_prob(p, v, u, delta, formula_49) CTS assume that the demonstrated skills form a tree, the domain reward function is known and the best model for merging a pair of skills is the model selected for representing both individually. CST is much faster learning algorithm than skill chaining. CST can be applied to learning higher dimensional policies. Even unsuccessful episode can improve skills. Skills acquired using agent-centric features can be used for other problems. CST has been used to acquire skills from human demonstration in the PinBall domain. It has been also used to acquire skills from human demonstration on a mobile manipulator.
Algorithm
CST uses an incremental MAP (maximum a posteriori) change point detection algorithm to segment each demonstration trajectory into skills and integrate the results into a skill tree.