^January February – 2011 ^March

Paper (1): "Feature based Locomotion Controllers" - abstract: This paper introduces an approach to control of physics-based characters based on high-level features of movement, such as center-of-mass, angular momentum, and end-effectors. Objective terms are used to control each feature, and are combined by a prioritization algorithm. We show how locomotion can be expressed in terms of a small number of features that control balance and end-effectors. This approach is used to build controllers for human balancing, standing jump, and walking. These controllers provide numerous benefits: human-like qualities such as arm-swing, heel-off, and hip-shoulder counter-rotation emerge automatically during walking; controllers are robust to changes in body parameters; control parameters and goals may be modified at run-time; control parameters apply to intuitive properties such as center-of-mass height; and controllers may be mapped onto entirely new bipeds with different topology and mass distribution, without modifications to the controller itself. No motion capture or off-line optimization process is used.

Paper (2): "Robust Physics based Locomotion Using Low Dimensional Planning" - abstract: This paper presents a physics-based locomotion controller based on online planning. At each time-step, a planner optimizes locomotion over multiple phases of gait. Stance dynamics are modeled using a simplified Spring-Load Inverted (SLIP) model, while flight dynamics are modeled using projectile motion equations. Full-body control at each instant is optimized to match the instantaneous plan values, while also maintaining balance. Different types of gaits, including walking, running, and jumping, emerge automatically, as do transitions between different gaits. The controllers can traverse challenging terrain and withstand large external disturbances, while following high-level user commands at interactive rates.

We consider the vertex coloring problem in the message-passing model of distributed computing. In this model the network is represented by a graph G of maximum degree Delta, in which the vertices host processors, and the communication is performed over the edges of G. Vertex coloring has numerous applications in communication networks, and thus it has drawn a considerable attention of researchers in the last three decades. The question of how many colors an efficient algorithm (that is, an algorithm with polylogarithmic time) is required to use is a central long-standing open question. Currently, efficient randomized algorithms that employ Delta + 1 colors are known, but it is unknown whether this number of colors can be achieved deterministically and efficiently. In 1987, in a seminal FOCS paper, Linial devised an efficient deterministic algorithm that employs Delta^2 colors. In his paper Linial also asked whether it is possible to employ a significantly smaller number of ! colors while still maintaining a deterministic algorithm with polylogarithmic running time. Despite a very intensive research in this direction in the last twenty years, this question remained open prior to our work. We present a deterministic algorithm that runs in polylogarithmic time, and employs Delta^{1 + epsilon} colors, for an arbitrarily small positive constant epsilon. Thus, our algorithm settles the long-standing question of Linial. Moreover, our results give rise to significantly improved algorithm for O(Delta)-coloring, and even for o(Delta)-coloring of very wide graph families. These results are achieved using a novel graph-decomposition technique. Specifically, the vertex set of the graph is partitioned into subsets that satisfy certain helpful properties. In particular, the subsets induce sparse subgraphs. This allows coloring the subgraphs with sufficiently small number of colors while utilizing the parallelism of the network to the full extent. Our recent results show that this technique is very powerful, and is useful for additional problems such as edge coloring.