Priority queue | EPFL Graph Search

In computer science, a priority queue is an abstract data-type similar to a regular queue or stack data structure. Each element in a priority queue has an associated priority. In a priority queue, elements with high priority are served before elements with low priority. In some implementations, if two elements have the same priority, they are served in the same order in which they were enqueued. In other implementations, the order of elements with the same priority is undefined. While priority queues are often implemented using heaps, they are conceptually distinct from heaps. A priority queue is an abstract data structure like a list or a map; just as a list can be implemented with a linked list or with an array, a priority queue can be implemented with a heap or another method such as an unordered array. Operations A priority queue must at least support the following operations:

is_empty: check whether the queue has no elements.
insert_with_priority: add an e

Inverse kinematics techniques of the interactive posture control of articulated figures

The context of this thesis is the interactive manipulation of complex articulated figures by means of geometric constraints (here called tasks), for the purpose of posture control and design. The goal is to determine a posture satisfying a set of prescribed tasks, usually expressed in the Cartesian space. This approach is known as Inverse Kinematics, and a number of analytic and numerical resolution methods have been developed for the control of robot manipulators. These methods have been applied to the computer animation of articulated figures, and to the control of human models for computer-aided ergonomic evaluations of products or workplaces. When dealing with figures that possess a large number of degrees of freedom, such as animal or human figures, their posture is usually controlled by several simultaneous tasks. There are tasks of different nature and function: they can control extremities such as the hands and the feet (for reaching or supporting purposes), as well as the center of mass, for balance control. They can also be used to avoid collisions with surrounding obstacles. The concurrent resolution of multiple tasks inevitably leads to conflicts that must be resolved with an appropriate strategy. A typical policy is to find a compromise solution that considers weights assigned to each task to indicate their relative importance. However, no task is precisely satisfied with this approach, and selecting appropriate weights is not always straightforward. In this thesis, we introduce a priority strategy for conflict resolution. With this policy, a task is not affected by other tasks of lower priority, and is satisfied as much as possible without affecting tasks of higher priority. The relative priority between two tasks is thus strictly enforced, which is appropriate for situations that cannot tolerate compromises. For example, keeping balance is more important than reaching an object with a hand, and avoiding inter-penetration of bodies is more important than any other task. Priorities are well-suited to express such hierarchical relationships. Based on a task-priority algorithm developed in robotics for simple manipulators, we introduce a framework that integrates the two conflict resolution strategies: first, the priorities assigned to the tasks are considered and, second, a weighting strategy solves the conflicts between tasks having same priority. We have improved the efficiency of the original algorithm by means of recursive relations, which is beneficial for interactive applications. Joint limits and joint couplings are also integrated in the framework to avoid unfeasible body postures. An interactive application, called BALANCE, has been developed to test the algorithm with a palette of task types: it allows us to illustrate the utility of task priorities for the manipulation of generic articulated figures, and of human models in particular. Besides simple geometric tasks, the application also proposes a task to keep the figure balanced under a set of static forces due to the interaction with its environment. It is shown that this task is easily integrated in the inverse kinematics framework, and that it is useful to generate postures in multiple supports with force exertions such as push and pull activities.

EPFL2001

Learning from demonstration using products of experts: Applications to manipulation and task prioritization

Sylvain Calinon, Emmanuel Pignat

Probability distributions are key components of many learning from demonstration (LfD) approaches, with the spaces chosen to represent tasks playing a central role. Although the robot configuration is defined by its joint angles, end-effector poses are often best explained within several task spaces. In many approaches, distributions within relevant task spaces are learned independently and only combined at the control level. This simplification implies several problems that are addressed in this work. We show that the fusion of models in different task spaces can be expressed as products of experts (PoE), where the probabilities of the models are multiplied and renormalized so that it becomes a proper distribution of joint angles. Multiple experiments are presented to show that learning the different models jointly in the PoE framework significantly improves the quality of the final model. The proposed approach particularly stands out when the robot has to learn hierarchical objectives that arise when a task requires the prioritization of several sub-tasks (e.g. in a humanoid robot, keeping balance has a higher priority than reaching for an object). Since training the model jointly usually relies on contrastive divergence, which requires costly approximations that can affect performance, we propose an alternative strategy using variational inference and mixture model approximations. In particular, we show that the proposed approach can be extended to PoE with a nullspace structure (PoENS), where the model is able to recover secondary tasks that are masked by the resolution of tasks of higher-importance.

SAGE PUBLICATIONS LTD2021

Managing Tail Latency in Datacenter-Scale File Systems Under Production Constraints

Ricardo Bianchini, Maria Fernanda Borge Chavez, Willy Zwaenepoel

Distributed file systems often exhibit high tail latencies, especially in large-scale datacenters and in the presence of competing (and possibly higher priority) workloads. This paper introduces techniques for managing tail latencies in these systems, while addressing the practical challenges inherent in production datacenters (e.g., hardware heterogeneity, interference from other workloads, the need to maximize simplicity and maintainability). We implement our techniques in a scalable distributed file system (an extension of HDFS) used in production at Microsoft. Our evaluation uses 70k servers in 3 datacenters, and shows that our techniques reduce tail latency significantly for production workloads.

ASSOC COMPUTING MACHINERY2019

Inverse kinematics techniques of the interactive posture control of articulated figures

EPFL2001