Performance of Averaging Algorithms in Time-Varying Networks

We study averaging algorithms in time-varying networks, and means tomeasure their performance. We present sufficient conditions on these algorithms, which ensure they lead to computation at each node, of the global average of measurements provided by each node in the network. Further, we present and use results from ergodic theory to define an accurate performance metric for averaging algorithms. This metric, the contraction coefficient, differs from previously used metrics such as the second largest eigenvalue of the expected weighting matrix, which gives an approximation of the real convergence rate only in some special cases which are hard to specify. On the other hand, the contraction coefficient as set forth herein characterizes exactly the actual asymptotic convergence rate of the system. Additionally, it may be bounded by a very concise formula, and simulations show that this bound is, at least in all studied cases, reasonably tight so as to be used as an approximation to the actual contraction coefficient. Finally, we provide a few results and observations which make use of the derived tools. These observations may be used to find new optima for design parameters of some averaging algorithms, and also open the door to new problems in the study of the underlying mathematical models.

Rigid body dynamics simulation for robot motion planning

Alan Ettlin

The development of robot motion planning algorithms is inherently a challenging task. This is more than ever true when the latest trends in motion planning are considered. Some motion planners can deal with kinematic and dynamic constraints induced by the mechanical structure of the robot. Another class of motion planners fulfill various types of optimality conditions, yet others include means of dealing with uncertainty about the robot and its environment. Sensor-based motion planners gather information typically afflicted with errors about a partially known environment in order to plan a trajectory therein. In another research area it is investigated how multiple robots best cooperate to solve a common task. In order to deal with the complexity of developing motion planning algorithms, it is proposed in this document to resort to a simulation environment. The advantages of doing so are outlined and a system named Ibex presented which is well suited to support motion planner development. The developed framework makes use of rigid body dynamics algorithms as simulation kernel. Further, various components are included which integrate the simulation into existing engineering environments. Simulation content can be conveniently developed through extensions of well-established 3D modelling tools. The co-simulation with components from other domains of physics is provided by the integration into a leading dynamic modelling environment. Robotic actuator models can be combined with a rigid body dynamics simulation using this mechanism. The same configuration also allows to conveniently develop control algorithms for a rigid body dynamics setup and offers powerful tools for handling and analysing simulation data. The developed simulation framework also offers physics-based models for simulating various sensors, most prominently a model for sensor types based on wave propagation, such as laser range finding devices. Application examples of the simulation framework are presented from the mobile robotics rough-terrain motion planning domain. Three novel rough-terrain planning algorithms are presented which are extensions of known approaches. To quantify the navigational difficulty on rough terrain, a new generic measure named "obstacleness" is proposed which forms the basis of the proposed algorithms. The first algorithm is based on Randomised Potential Field Planners (RPP) and consequently is a local algorithm. The second proposed planner extends RRTconnect , a bi-directional Rapidly Exploring Random Tree (RRT) algorithm and biases exploration of the search space towards easily traversable regions. The third planner is an extension of the second approach and uses the same heuristic to grow a series of additional local RRTs. This allows it to plan trajectories through complex distributions of navigational difficulty benefitting from easy regions throughout the motion plan. A complete example is shown in which the proposed algorithms form the basis for sensor-based dynamic re-planning simulated in the presented framework. In the scenario, a simulated planetary rover navigates a long distance over rough terrain while gathering sensor data about the terrain topography. Where obstacles are sensed which interfere with the original motion plan, dynamic re-planning routines are applied to circumnavigate the hindrances. In the course of this document a complete simulation environment is presented by means of a theoretical background and application examples which can significantly support the development of robot motion planning algorithms. The framework is capable of simulating setups which fulfil the requirements posed by stateof-the-art motion planning algorithm development.

EPFL2006

Caractérisation de la génération et la propagation d'ondes de pressions dans des tissus biologiques pour la conception d'appareils médicaux

Mathieu Benoit

Therapies using so called extracorporeal shock waves (Extracorporeal Shock Wave Therapy ESWT) have become current medical practice in orthopedy and traumatology. In order to understand and to optimize the effect of shock waves in clinical applications, medical results must be correlated with well characterized mechanical stimuli. This thesis has an industrial scope. It contributes to the comprehension of the generation and propagation of pressure waves in human tissues with the aim of improving existing ESWT therapies and of providing the industrial partner with tools for the design of a new generation of extracorporeal shock waves devices. The adopted general approach is based on a combination of experimental characterization and analytical and numerical modeling of wave generation and propagation phenomena in a medical treatment device and in biological tissues. Firstly, the characterization of a wave generator is based, on the one hand, on measurements of the dynamic behavior of the moving parts coupled with rigid body simulation, and on the other hand on measurements of wave propagation by means of a Hopkinson bar coupled with finite elements simulations. This characterization has shown that the generator produces very reproducible stress pulses. The simulation technique allows designing a new wave generator with a higher energy range and with well controlled operating parameters. The new design is covered by a patent. Secondly, a measurement technique for generation and propagation of pressure waves in soft animal tissues has been developed that is based on PVDF gages. The applicability of these gages has been qualitatively validated by comparative measurements with a Hopkinson bar. The perturbation effect of the gage, acting as an inclusion in the medium to be characterized, has been evaluated by means of simulations of wave propagation in water. Comparison with measurements in soft tissues suggests that it is negligible for pressure measurement in this type of materials. An independent calibration of the gage could however not be performed. Finally, measurements of wave propagation in pig skin and fat using PVDF gauges showed good reproducibility for a given sample. They highlighted the influence of the supply pressure of the wave generator on the amplitude and on the attenuation of the wave in tissues. Moreover, the dependence between the amplitude of the wave and its propagation velocity suggests a non-linear viscoelastic behavior of soft tissues as well as the need of a constitutive model for high strain rates. Simulations of wave propagation using a known hyperelastic constitutive model highlighted the difficulty of modeling such soft tissues. A viscoelastic non-linear constitutive model based on power laws was considered and is an interesting candidate for future simulations. The simulation technique for wave generation and propagation in a solid (aluminum) and a liquid (water) has been validated by comparing its results with measurements performed in these materials (strain gages and PVDF hydrophone respectively). Simulations of pressure wave propagation validated for solids and liquids showed that they can be applied to biological tissues modeled using a known constitutive model; they are a tool for any other simulation using more complex constitutive models. This work contributes to a broader study aimed at establishing and validating constitutive models for biological materials suitable for use in simulations of wave propagation.

EPFL2009

Radiative Backpropagation: An Adjoint Method for Lightning-Fast Differentiable Rendering

Wenzel Alban Jakob, Merlin Eléazar Nimier-David, Sébastien Nicolas Speierer

Physically based differentiable rendering has recently evolved into a powerful tool for solving inverse problems involving light. Methods in this area perform a differentiable simulation of the physical process of light transport and scattering to estimate partial derivatives relating scene parameters to pixels in the rendered image. Together with gradient-based optimization, such algorithms have interesting applications in diverse disciplines, e.g., to improve the reconstruction of 3D scenes, while accounting for interreflection and transparency, or to design meta-materials with specified optical properties. The most versatile differentiable rendering algorithms rely on reverse-mode differentiation to compute all requested derivatives at once, enabling optimization of scene descriptions with millions of free parameters. However, a severe limitation of the reverse-mode approach is that it requires a detailed transcript of the computation that is subsequently replayed to back-propagate derivatives to the scene parameters. The transcript of typical renderings is extremely large, exceeding the available system memory by many orders of magnitude, hence current methods are limited to simple scenes rendered at low resolutions and sample counts. We introduce radiative backpropagation, a fundamentally different approach to differentiable rendering that does not require a transcript, greatly improving its scalability and efficiency. Our main insight is that reverse-mode propagation through a rendering algorithm can be interpreted as the solution of a continuous transport problem involving the partial derivative of radiance with respect to the optimization objective. This quantity is "emitted" by sensors, "scattered" by the scene, and eventually "received" by objects with differentiable parameters. Differentiable rendering then decomposes into two separate primal and adjoint simulation steps that scale to complex scenes rendered at high resolutions. We also investigated biased variants of this algorithm and find that they considerably improve both runtime and convergence speed. We showcase an efficient GPU implementation of radiative backpropagation and compare its performance arid the quality of its gradients to prior work.

ASSOC COMPUTING MACHINERY2020