Branched constraint sets for multi-modal obstacle predictions.
- Existing works accounting for prediction uncertainty:
- Compute the single most-likely prediction, which may be overly optimistic and requires the environment to cooperate.
- Account for all prediction outcomes, which can be overly conservative and may lead the robot to stand stuck. - Improvement: the robot is able to make progress while planning to react when the necessary information becomes available in the future.
- Multi-world motion planning formulation:
- x(t, i) and u(t, i) are the state and action at time step t and branch i.
- p(t, i) is the index of the parent branch at t-1 of branch i at time t, which could be itself if no split happens from t-1 to t.
- Personal thoughts:
- In receding horizon planning, the point of planning for a longer horizon is just so that we don’t make extremely stupid move immediately, so it’s unnecessary to plan for future actions far ahead to avoid all possibilities at that time.
- With branched constraint sets, a generated trajectory is no longer an action sequence, but a tree structure that takes account of potential recourse.
- Here the state and dynamics only account for the robot itself, whereas the obstacle evolvement is reflected in the time-dependent obstacle set, which thus cannot be “reactive”.
- Personally, I take the approach in this paper as a middle ground between (1) deterministic optimal control, where everything is assumed to be known a-priori and often leads to convex optimization, and (2) heuristic search in a bushy game tree, where branching happens at every time step and an opponent’s move (environmental change) is stochastically dependent on the agent’s action. - Thee-step algorithm:
- split detection based on sampled obstacle trajectories;
- split-aware space-time RRT for coarse-grained trajectory generation;
- split-aware iLQR for fine-grained trajectory optimization. - Split detection fits Gaussian Mixture Models (GMM) to sampled predictions at each future time step.
- A partitioning is separable if a condition for classification confidence and a condition for quality of approximation are both satisfied.
- Essentially, it needs to ensure for each sample there is a Gaussian subset that has a significantly high likelihood.
- Two Gaussians are separable if their max approximates their sum. - Split-aware space-time RRT:
- An RRT node consists of the states of all the branches at a time step.
- At each iteration, first sample t, and independently sample one state for each branch at t.
- A node on the tree is considered as the nearest neighbor to the sample if the sum of the distances from the sampled states to their ancestor states in the node is minimum. (Note that this is only proportional to the number of states in the new sample, and thus is comparable among existing tree nodes.)
- Intermediate split points are added to connect the sample with the nearest neighbor.
- A sample is added only when the paths from all the states to their ancestors in the nearest neighbor are collision free.
- An RRT path is considered as colliding if it falls within the 3-sigma of any of the Gaussian obstacles. - Split-aware iLQR:
- The cost-to-go of a pre-split state is dependent on the expectation of the values of all the child states, but is still quadratic.
- The time complexity per iteration is proportional to the total number of branches across all the time steps.
References:
- Bobby Davis, Nicholas Sohre, and Stephen J. Guy. Multi-World Motion Planning. IEEE RA-L, 2018
