Constructing skill trees (CST) is a hierarchical reinforcement learning algorithm which can build skill trees from a set of sample solution trajectories obtained from demonstration.
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.
CST was introduced by George Konidaris, Scott Kuindersma, Andrew Barto and Roderic Grupen in 2010.
[1] 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
A particle filter is used to control the computational complexity of CST.
The change point detection algorithm is implemented as follows.
A linear regression model with Gaussian noise is used to compute
Then, CST compute the probability of the changepoint at time j with model q,
The descriptions of the parameters and variables are as follows; The skill length l is assumed to follow a Geometric distribution with parameter p Using the method above, CST can segment data into a skill chain.
CST needs to align the component skills because the change-point does not occur in the exactly same places.
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.
This procedure is repeated until it fails to merge a pair of skill segments.
The following pseudocode describes the change point detection algorithm: 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 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.