I am a member of the Systems, Dynamics and Control group at UCLA. Below is a brief summary of my research. For related papers, please refer to my publications.

• Sampling-based algorithms for safety analysis
  • Masters thesis research (2002-2004): For my masters thesis, I worked with my advisor towards novel sampling based algorithms for safety falsification of hybrid systems. The safety falsification problem is a weaker version of the reachability problem which is in general known to be undecidable. The proposed algorithms have nice coverage properties on the state space but since they are randomized they can guarantee only probabilistic completeness. This means that the probability of such an algorithm disproving safety of the system (assuming it is true) goes to 1 as the number of samples goes to infinity. However, if they are terminated after a finite number of samples are generated, and safety is not disproved till that point, then these algorithms become inconclusive. Moreover these algorithms can only analyze safety over finite time horizon.

At the left, is a simple example of the shortcoming of a probabilistically complete algorithm for the purpose of safety analysis of systems. The system is a point mass moving on a plane with bounded speed. The trajectories were constructed incrementally using Rapidly Exploring Random Trees(RRT), a probabilistically-complete algorithm. Terminating the search procedure before the unsafe set is reached makes the result inconclusive.

• Doctoral dissertation research (2004-present): For my doctoral research, I have been looking at ways to achieve completeness results for sampling-based algorithms for safety falsification problem. To resolve the problem of incomplete behavior of the algorithm over finite iterations, and to analyze safety over infinite time horizon, we have proposed sampling based algorithms that are resolution-complete. What this means is that these algorithms are guaranteed to terminate in finite time for given resolution of inputs. The algorithms use the search for a counter example to safety to generate a safety certificate (if no counter example is found). As a result, at termination they return either a feasible counterexample or prove by construction of a safety certificate that the system behaves safely when the inputs are restricted to a smaller class. We have proposed two notions of resolution completeness and have proposed algorithms for linear continuous and hybrid systems.

At the left is shown a typical end result of using a resolution-complete sampling-based algorithm for safety falsification. The system is a second order LTI continuous-time system with exogenous inputs. The algorithm used is based on Depth-First-Search with Branch and Bound (called as DFS-BB). In case no proof of unsafety is found, a proof of safety for restricted class of inputs is generated.

Work is currently underway to develop more efficient heuristics and to investigate if similar ideas can be used for nonlinear systems.

• Consensus Problems (2007-present): Another line of work that I have been following recently is for consensus problems for mobile agents with non trivial dynamics. One such instance of consensus problems is the rendezvous problem where the participating agents have to agree on time of arrival at a fixed (known or unkown) destination point. I have investigated the version where the destination point is known in advance and the agents have to arrive there in minimum possible (but same) time while achieving maximum spread in terms of arrival angles at the destination point. The agents are assumed to be Dubins vehicles. I have proposed a provably correct approximation algorithm that is decentralized and using which the vehicles arrive at destination in minimum possible time. Below is shown a minimum-time rendezvous of 4 vehicles at the target.

We are currently working on implementation of this algorithm on the Multi-UAV testbed (part of the ARES Lab, LIDS, MIT).

• Satellite orbit design (2001-2002): As part of my undergraduate thesis, I conducted feasibility studies of using satellites in non-geostationary orbits. The motivation behind this idea was that such orbits could offer significant fuel savings and could be used for communication and other purposes at least in countries close to equator. My work investigated the advantages offered and the challenges involved in using such orbits over the Indian subcontinent.
• Other areas

Besides the above mentioned research topics, I am also interested in verification methods for software programs, logic based specifications for hybrid systems, motion planning algorithms and parametric programming. However my knowledge and experience in these areas is currently limited to their use in my own line of research or their relation to my work.