Research
Research
- Consensus-based Distributed Optimization (2011, 2012)
We study the role of the network in consensus-based distributed optimization using Distributed Dual Averaging as prototypical paradigm. More specifically, we study the effects of using general consensus protocols and communication delays. Non-doubly stochastic consensus protocols can introduce bias in the objective function being optimized. We show how to correct the bias for row stochastic protocols. Furthermore, we show that in the presence of bounded communication delays convergence to the optimum at a rate O(T-0.5) is still possible. In more recent work we propose a new algorithm called Push-Sum Distributed Dual Averaging (PS-DDA) and discuss the many practical advantages it has both in terms of implementation and theoretical analysis.
Related Papers: ACC, CDC
- Modelling Communication Delays (2011)
In the areas of distributed consensus and optimization where we are interested in computing or optimization a function over a network, the role of the network and the communication delays that could be introduced is critical. Do delays slow down the computation? Do they affect convergence? In this project we propose two novel ways to model communication delays by augmenting a network with delay nodes. This allows us to analyze the effect of delays using techniques from non-reversible Markov chains. E.g., for consensus problems when each link experiences a fixed (and not the same per link) amount of delay, we can compute the consensus value exactly and bound the convergence rate by the second largest eigenvalue of a stochastic transition matrix describing the consensus protocol.
Related Paper: Allerton
Code (Matlab)
- Multiscale Gossip for Fast Averaging (2010)
We consider the problem on distributed averaging in sensor networks. To improve the longevity of a network we need algorithms that can reach consensus to the average using a minimal number of transmissions. In this project we develop an algorithm which converges w.h.p. using O(n loglogn) number of transmissions on Random Geometric Graphs with n nodes Our algorithm computes the average by hierarchically splitting the graph and solving a number of subproblems whose local averages are then combined. This approach limits the maximum distance that any multi-hop message needs to travel and balances the number of transmissions that each node has to make.
Related Papers: DCOSS, Trans. on Signal Processing
- Complex Bezier Curves and B-Splines (2009)
Bezier curves and B-splines are standard tools for computer aided design. Fractals are seemingly very different geometric objects. Theoretical connections between the two however exist showing that Bezier curves and B-splines are fractals. In this work we show the other directions i.e. that fractals that can be generated by iterated function systems are in fact equivalent to Bezier curves or B-splines with knots on the complex domain. We show how to generate fractals using standard tools like the De Castlejaw algorithm or Boehm's know insertion for B-splines. Two major new possibilities arise. We can now have fractals with control points that can be moved to transform a fractal intuitively and since we view fractals as polynomial curves we can have fractal parametrizations.
Related Paper: Fractals
Code (Mathematica): Bezier Curves
Code (Mathematica): B-splines
- Replanning: A motion planning strategy for solving hard kinodymaic problems (2008)
Sampling-based planners are usually thought of as offline planners which try to find a trajectory through some hard narrow passage. Typical problems include the need for possibly unbounded amounts of memory and the generation of trajectories that include a lot of redundant motions. Those problems are more pronounced if a robot has realistic motion constraints (e.g., bounded acceleration) and physical effects such are gravity and friction are modeled. This work describes a sampling-based kinodynamic motion planner that solves hard problems using replanning. The overall planning process is broken down into replanning cycles. In each cycle, a sampling-based planner is invoked for a small amount of time to produce a kinodynamic tree of possible future motions. Then a navigation function is used to evaluate these motions and select the one that brings the robot closer to its goal.
This approach has the advantage that it uses only bounded memory. Moreover, it has been shown experimentally that the produced paths are much shorter than those of state-of-the art sampling-based planners. In addition this algorithm was able to solve harder problems more consistently. These results agree on experiments with a segway and a blimp. Finally, due to the adaptive nature of replanning, this method can be extended to problems where the robot encounters unexpected obstacles and also moving obstacles.
Related Paper: IROS
Video : A segway is moving to its goal while avoiding newly sensed unexpected static obstacles. Is also avoids moving obstacles that are assumed to be fully predictable here
Video : A blimp flies to its goal by hovering among two parallel plates
- Distributed Multi-robot exploration (2007)
- Safe Mulit-Robot Planning under kinodynamic constraints (2007)
This is a powerful extension of the project described below. Equipped with the algorithmic requirements for safety, it is of interest to coordinate a team of robots in a fully distributed fashion with a message passing algorithm using only local neighborhood information. The robots replan their motions periodically as they move. Each robot plans in its own state space and produces a set of possible motions. Then a properly formalized version of Belied Propagation is used to come up with motion selections that take the robots to their goals safely. This algorithm was implemented and tested on a cluster with each robot being simulated on a different processor and communication is achieved via sockets using simple send and receive messages.
Related Papers: ROBOCOMM, MONET
Video : Exploration of a 2D building using 5 robots
Video : Exploration of a 2D scene of random polygonal obstacles with 10 robots
- Distributed Formation Planning (2005)
For any team of robots to be useful in a practical application, it is important to guarantee that the robots can move to their goals without colliding with their static environment or with each other. The problem becomes hard when we consider realistic (second order) kinodynamic constraints in the robot's motion. This work describes how to utilize communication to guarantee the safety of the robots in the team. It turns out that It is enough to satisfy three requirements in the motion planner and the coordination algorithm. The algorithm has been tested using a simple decentralized coordination scheme based on priorities.
Related Paper: IROS
I completed this project for my diploma thesis under the supervision of Prof Nikos Vlassis. A team of robots try to create a formation and then move as a team preserving that formation. Each robot has five possible actions; move 1 unit Up,Down,Left, Right or stay still. Robots within an 8-connectivity neighborhood can communicate but no other global information is available. The robots coordinate using a Belief Propagation variant called Max-Plus. This is an increasingly popular distributed message passing algorithm for probabilistic inference.
Video
