I am a Research Scientist with the Department of Computer and Information Science, which is part of School of Engineering and Applied Science, University of Pennsylvania. I am also a member of the GRASP laboratory.

email: myusername@seas.upenn.edu, where myusername is the word right after tilde in the URL of this website
office #: GRW 376
address: 3330 Walnut St, Levine Hall, Philadelphia, PA 19104

Publications

Full CV

Personal

   Research: My general research interests lie in Artificial Intelligence and Robotics. More specifically, they currently cover planning in deterministic and probabilistic domains and machine learning. So far, my research has been mainly motivated by the problem of fast and intelligent decision making by autonomous robotic systems in real-world environments. I do get easily motivated, however, by other interesting problems in AI.

During my 2-year Postdoctoral Fellowship at CMU, I worked with Tony Stentz on multi-agent planning with adversaries. During the same time, I have also worked on the design and implementation of a complex maneuvering planner for the CMU vehicle that WON the Urban Challenge race (the third DARPA Grand Challenge). During my Ph.D. studies at CMU, my advisors were Geoff Gordon and Sebastian Thrun (presently at Stanford). Before enrolling into the Ph.D. program at CMU I have been a Ph.D. student for two years in the College of Computing at Georgia Tech where I worked with Ronald Arkin at Mobile Robot Laboratory and Sven Koenig.

Personal: Since the birth of our daughter Alexandra, the personal life of our family mainly revolves around her, ...with the big help of our parents and grandparents :).



Selected Research Projects
I develop algorithms that solve large-scale real world planning and decision-making problems with uncertainty and real-time performance requirements. I strive to equip these algorithms with a solid theoretical analysis and use them to provide efficient and robust planning in real robotic systems including mobile robots navigating at high-speeds in partially-known environments, multi-robot systems operating in hostile environments and autonomous vehicles navigating urban environments such as the CMU vehicle that won the 1st place in the Urban Challenge race in 2007 (the 3rd DARPA Grand Challenge competition).

Planning under uncertainty
Probabilistic Planning with Clear Preferences (PPCP): In many real-world problems, the agent has to operate in an environment that is only partially known. Examples of such problems include robot navigation, route planning under changing traffic conditions, air traffic management with changing weather conditions, and many others. Ideally, in all of these situations, a planner must produce a plan which reasons over the probability distribution over all the possible instances of the environment. Unfortunately, such planning corresponds to POMDP (Partially Observable Markov Decision Processes) planning and is known to be intractable. For many of these problems, however, one can clearly name in advance the best (preferred) values of the variables that represent the unknowns in the environment. Thus, in the robot navigation problem, for example, it is always preferred to find out that an initially unknown location is traversable rather than not. In the problem of route planning, it is always preferred to find out that there is no traffic on the road of interest. And in the air traffic management problem, it is always preferred to have a good flying weather. In this work, Tony Stentz and I use this property to show how this seemingly very difficult and high-dimensional planning problem can be solved by running a series of simple and fast low-dimensional A*-like searches. The developed algorithm, called PPCP (Probabilistic Planning with Clear Preferences), is fast, scales to very large problems, and can guarantee optimality under certain conditions. The problems it solves contain billions of states; this is several magnitudes more than that which the current preeminent POMDP solvers can handle. PPCP is also a widely applicable algorithm, and we have just started to apply it to different domains. To this point, it has been used to solve the problem of robot navigation in partially known environments, and the problem of robot navigation with multiple scout robots in the environment that contains a number of possible adversary locations (PPCP paper, AAAI'06).
Planning for main robot and team of scouting helicopters in the environment with possible adversaries (The task is for the main robot to get to its goal without being detected by an adversary, the scouting helicopters are used to sense for adversaries. Here is a full movie ):

3.2 by 3.5 km environment
PPCP policy after convergence (30 secs)
scouting helicopters on mission
locations A & B sensed (adversary in A)
location C sensed (no adversary discovered)

scout moves towards location D
location D sensed (no adversary discovered)
main robot on the way to its goal
main robot reaches its goal
Planning for Markov Decision Processes with Sparse Stochasticity (MCP): Real-world planning problems often exhibit uncertainty, which forces us to use the slower algorithms to solve them. However, many real-world planning problems exhibit sparse uncertainty: there are long sequences of deterministic actions which accomplish tasks like moving sensor platforms into place, interspersed with a small number of sensing actions which have uncertain outcomes. In this work, together with Geoff Gordon and Sebastian Thrun we have developed a new planning algorithm, called MCP (short for MDP Compression Planning), which combines A* search with value iteration for solving Stochastic Shortest Path problem in MDPs with sparse stochasticity. We present experiments which show that MCP can run substantially faster than competing planners in domains with sparse uncertainty; these experiments are based on a simulation of a ground robot cooperating with a helicopter to fill in a partial map and move to a goal location (MCP paper, NIPS'04).
Planning with MCP for the robot-helicopter coordination problem (here is a movie):

3D data
traversability map
robot and helicopter executing the policy generated by MCP


Planning under time constraints
Anytime D*: In this work, together with Dave Ferguson, Geoff Gordon, Tony Stentz and Sebastian Thrun, we develop a graph-based planning and replanning algorithm able to produce bounded suboptimal solutions in an anytime fashion. Our algorithm tunes the quality of its solution based on available search time, at every step reusing previous search efforts. When updated information regarding the underlying graph is received, the algorithm incrementally repairs its previous solution. The result is an approach that combines the benefits of anytime and incremental planners to provide efficient solutions to complex, dynamic search problems (Anytime D* paper, ICAPS'05, draft version of a long paper on anytime incremental search, Artificial Intelligence Journal (accepted for publication)).
Planning with Anytime D* for various robotic systems:

using Anytime D* on ATRV (Here is a movie showing a run and a movie showing how ATRV builds a map and Anytime D* re-plans paths.)
using Anytime D* on Segbot (Here is a movie showing the segbot building a map while being controlled by Anytime D*.) 		     
using Anytime D* for parking maneuvers for the CMU vehicle (Boss) that won the 1st place in the DARPA Urban Challenge race in 2007
Anytime A* with Provable Bounds on Sub-Optimality (ARA*): In real world planning problems, time for deliberation is often limited. Anytime planners are well suited for these problems: they find a feasible solution quickly and then continually work on improving it until time runs out. In this work, together with Geoff Gordon and Sebastian Thrun we propose an anytime heuristic search, ARA*, which tunes its performance bound based on available search time. It starts by finding a suboptimal solution quickly using a loose bound, then tightens the bound progressively as time allows. Given enough time it finds a provably optimal solution. While improving its bound, ARA* reuses previous search efforts and, as a result, is significantly more effi- cient than other anytime search methods (ARA* paper, NIPS'03).
Planning with ARA*:

Motion planning for 6 DOF robot arm. Here is a movie
Motion planning for 20 DOF robot arm. Here is a movie
Incremental versions of A* search (LPA*, D* Lite, Adaptive A*): Autonomous agents often have to operate in partially-known and/or dynamic environments. Consequently, they often have to re-plan based on new sensing information. Together with Sven Koenig, we have developed a series of incremental A* algorithms that can speed up repeated planning by orders of magnitude. Some of these algorithms, such as D* Lite and LPA*, have been used on a number of real robotic systems and are now taught in various universities (LPA* paper, NIPS'02, D* Lite paper, Transactions on Robotics and Automation'05, Real-Time Adaptive A* paper, AAMAS'06).