Papers Read

Sites

• Lucas Kovar
  • Motion Graphs
• Jehee Lee

• An Evaluation of a Cost Metric for Selecting Transitions between Motion Segments
  • Jing Wang and Bobby Bodenheimer. 2003. Eurographics.
  • cost function. compute a set of optimal weights, using a constrained least-squares technique.

Fat Graphs: Constructing an interactive character with continuous controls

Hyun Joon Shin and Hyun Seok Oh. 2006. [website]

Parametric motion graphs

Rachel Heck and Michael Gleicher. 2007. [website]

• graph: a parameterized motion graph
• node: a parametric motion space implemented using blending-based parametric synthesis [Kovar and Gleicher (2004)]
• The parameterized motion space represented by node \(\mathrm{N}_i\) is denoted by \(\mathcal{P}^i (l)\), where \(l\) is a vector of relevant motion parameters, such as the target of a punch; a parametric motion space produces a short motion, \(\mathrm{M}_i\), for any given value, \(l_i\), of its continuously valued parameters.
• The key challenge is finding a way to identify and represent possible transitions between these parameterized nodes.
• This paper says our surrogate low level controller's linear blending as one solution of the 'traditional synthesis-by-concatenation problem'. When each node accepts only a single point as a valid parameter, the 'key challenge' falls within this problem.
• edge: an edge between source and target nodes maps any point \(l_i^s\) in \(\mathcal{P}^s\) to the subspace of \(\mathcal{P}^t\) that can be transitioned to from \(\textrm{M}_i^s = \mathcal{P}^s(l_i^s)\). We draw about 50 samples from \(\textrm{N}_s\), and about 1000 samples from \(\textrm{N}_t\). We calculate all the transitions from a certain sample \(l_i^s\) to \(L^t\). Then, find a bounding box that specifies the space containing all the possible target transition points in \(\textrm{N}_t\). Putting all the pieces together, an edge can be defined between \(\textrm{N}_s\) and \(\textrm{N}_t\) as a list of transition samples, one for each parameter vector in \(L_s\). Each sample includes:
  • the value of the parameter vector \(l_i^s\),
  • the computed transition bounding box for \(l_i^s\), and
  • the average, normalized transition point for \(l_i^s\).
• Given the node \(N_s\), and relevant parameter vector \(\tilde{l}^s\), find the k-nearest neighbors within the transition sample list in terms of Euclidean distance. Calculate an interpolating bounding box using these samples' transition bounding box.

Construction and optimal search of interpolated motion graphs

Alla Safonova and Jessica Hodgins. 2007. SIGGRAPH. [website]

• An anytime version of A* search. The key insight is that we represent the motion as an interpolation of two time-scaled paths through a motion graph.
• motion: an interpolation of two time-scaled paths through a motion graph. \(M'(t) = w(t)M_1(t) + (1-w(t))M_2(t)\).
  • unknowns: \(M_1(t), M_2(t)\) and \(w(t)\).
  • constraints: user specification.
  • objective function: the sum of the squared torques computed via inverse dynamics (~ energy needed to perform the motion) + the sum of the costs of the trasitions associated with the traversed edges in the motion graph (~ the smoothness of the motion).
• search method: graph, \(s_{start}\), \(s_{goal}\) as inputs. uses a problem-specific heuristic function, \(h(s)\), that estimates the cost of a path from \(s\) to \(s_{goal}\). \(h(s) \le c(s,s')+h(s')\), while \(s'\) is a successor of \(s\). The anytime extension of A* uses an inflated heuristic (\(h\) multiplied by \(\epsilon > 1\)). \(\epsilon\) times of cost sub-optimal.
• MG: motion graph \(S = (I)\)
• IMG: interpolated motion graph \(S = (I_1, I_2, w)\)
• ISG: full search graph, \(S\) is a state in IMG with additional \(P_x, P_z, Q_{yaw}\).
• A* takes \(O(E + S \log S)\). We need a compression!

Simulating biped behaviors from human motion data

Kwang Won Sok, Manmyung Kim and Jehee Lee. 2007. SIGGRAPH. [website]

SIMBICON: Simple biped locomotion control

KangKang Yin, Kevin Loken, and Michiel van de Panne. 2007. SIGGRAPH. [website]

• Locomotion involves joint limit constraints, torque-limit constraints, contact constraints, and contact impacts. Data-driven approaches have been very successful at generating kinematic models of locomotion, while it's hard to be implemented to dynamic simulations.
• Common approaches to locomotion control include:
  1. the use of passive walking as a starting point for the design of active walkers;
  2. the use of "zero moment point" control;
  3. using a fixed control architecture and applying parameter search to find the parameter settings that yield successful walking gaits; and
  4. developing feedback laws based upon insights into balance and locomotion.

Near-optimal character animation with continuous control

Adrien Treuille, YongJoon Lee, and Zoran Popović. 2007. SIGGRAPH. [pdf]

Variable resolution discretization in optimal control

Rémi Munos and Andrew Moore. 1999. IJCAI. [website]

1. Criteria Based on the Value Function
   1. average corner-value difference: splits wherever the value function is not constant
   2. value non-linearity: splits wherever the value function is not linear.
      we don't want to spend too much effort around the discontinuity of the VF whereas the control is constant in this area.
   3. policy disagreement: the performance is relatively weak, but it can be beneficially combined with other ones.
2. Influence and Variance
   • influence: the extent to which states affect globally the VF
   • influencers of state \(\xi\): the set of states \(\xi_i\) that have a non-zero influence on \(\xi\)
   • variance: which measures the amount of interpolation introduced by the discretization process.
   • gain of a sequence \(s(\xi)\): \(J(s(\xi)) = R(\xi) + \sum_{t \ge 1} \gamma^{\sum_{s=0}^{t-1} \tau(\xi(s))} R(\xi(t))\)
   • \(\forall s(\xi), V(\xi) = E[J(s(\xi))]\) ?
   • variance \(\sigma^2(\xi) = E[[J(s(\xi)) - V(\xi)]^2]\)
   • \(Stdev\_Inf(\xi) = \sigma(\xi) I(\xi|\Sigma)\)