Dmitri Dolgov

ICRA Conference 2009 Conference Paper

Autonomous driving in a multi-level parking structure

• Rainer Kümmerle
• Dirk Hähnel
• Dmitri Dolgov
• Sebastian Thrun
• Wolfram Burgard

Recently, the problem of autonomous navigation of automobiles has gained substantial interest in the robotics community. Especially during the two recent DARPA grand challenges, autonomous cars have been shown to robustly navigate over extended periods of time through complex desert courses or through dynamic urban traffic environments. In these tasks, the robots typically relied on GPS traces to follow pre-defined trajectories so that only local planners were required. In this paper, we present an approach for autonomous navigation of cars in indoor structures such as parking garages. Our approach utilizes multi-level surface maps of the corresponding environments to calculate the path of the vehicle and to localize it based on laser data in the absence of sufficiently accurate GPS information. It furthermore utilizes a local path planner for controlling the vehicle. In a practical experiment carried out with an autonomous car in a real parking garage we demonstrate that our approach allows the car to autonomously park itself in a large-scale multi-level structure.

ICRA Conference 2009 Conference Paper

Autonomous driving in semi-structured environments: Mapping and planning

• Dmitri Dolgov
• Sebastian Thrun

We consider the problem of autonomous driving in semi-structured environments (e. g. , parking lots). Such environments have strong topological structure (graphs of drivable lanes), but maneuvers with significant deviations from those graphs are valid and frequent. We address two main challenges of operating in such environments: i) detection of topological structure from sensor data, and ii) using that structure to guide path planning. We present experimental results on both of these topics, demonstrating robust estimation of lane networks in parking lots and the benefits of using these topological networks to guide path planning.

IS Journal 2008 Journal Article

AI's 10 to Watch

• James Hendler
• Philipp Cimiano
• Dmitri Dolgov
• Anat Levin
• PETER MIKA
• Brian Milch
• Louis-Philippe Morency
• Boris Motik

The recipients of the 2008 IEEE Intelligent Systems 10 to Watch award—Philipp Cimiano, Dmitri Dolgov, Anat Levin, Peter Mika, Brian Milch, Louis-Philippe Morency, Boris Motik, Jennifer Neville, Erik Sudderth, and Luis von Ahn—discuss their current research and their visions of AI for the future.

IROS Conference 2008 Conference Paper

Apprenticeship learning for motion planning with application to parking lot navigation

• Pieter Abbeel
• Dmitri Dolgov
• Andrew Y. Ng
• Sebastian Thrun

Motion and path-planning algorithms often use complex cost functions for both global navigation and local smoothing of trajectories. Obtaining good results typically requires carefully hand-engineering the trade-offs between different terms in the cost function. In practice, it is often much easier to demonstrate a few good trajectories. In this paper, we describe an efficient algorithm which - when given access to a few trajectory demonstrations - can automatically infer good trade-offs between the different costs. In our experiments, we apply our algorithm to the problem of navigating a robotic car in a parking lot.

IROS Conference 2008 Conference Paper

Local line segments as primitives for scene understanding

• Michael James 0001
• Dmitri Dolgov

With the increasing sophistication of sensors such as 3D laser range finders and their use in more complex environments, new approaches for the efficient processing of 2 and 3D point data are becoming more and more important. We develop algorithms for finding and using line segments as primitives for processing such data, and explore the benefits of such a choice. Line segments are simple enough to allow for relatively efficient detection algorithms, but are sophisticated enough to support tracking of dynamic obstacles over time. Further, such a parametric representation of the environment is better suited to deal with the noise inherent in dynamic, real-world environments. We develop a locally-adaptive line-detection algorithm, the output of which is used in a line-segment tracker. The resulting representation is shown to alleviate some of the problems in ray-tracing a dynamic obstacle map.

AAMAS Conference 2006 Conference Paper

Resource Allocation Among Agents with Preferences Induced by Factored MDPs

• Dmitri Dolgov
• Edmund Durfee

AAMAS Conference 2005 Conference Paper

Computationally-Efficient Combinatorial Auctions for Resource Allocation in Weakly-Coupled MDPs

• Dmitri Dolgov
• Edmund Durfee

IJCAI Conference 2005 Conference Paper

Stationary Deterministic Policies for Constrained MDPs with Multiple Rewards, Costs, and Discount Factors

• Dmitri Dolgov
• Edmund

We consider the problem of policy optimization for a resource-limited agent with multiple timedependent objectives, represented as an MDP with multiple discount factors in the objective function and constraints. We show that limiting search to stationary deterministic policies, coupled with a novel problem reduction to mixed integer programming, yields an algorithm for finding such policies that is computationally feasible, where no such algorithm has heretofore been identified. In the simpler case where the constrained MDP has a single discount factor, our technique provides a new way for finding an optimal deterministic policy, where previous methods could only find randomized policies. We analyze the properties of our approach and describe implementation results.

AAAI Conference 2005 Short Paper

Towards Exploiting Duality in Approximate Linear Programming for MDPs

• Dmitri Dolgov

A weakness of classical Markov decision processes is that they scale very poorly due to the flat state-space representation. Factored MDPs attempt to address this by exploiting problem structure. However, in general, solutions to factored MDPs do not retain the structure and compactness of the problem representation, forcing approximate solutions, with approximate linear programming (ALP) emerging as a very promising MDP-approximation technique. However, the ALP work has focused on approximating the primal LP, and no effort has been invested in approximating the dual LP, which serves as the basis for solving a wide range of constrained MDPs. Our analysis of the dual LP shows that a straightforward application of linear approximations is not as well-suited for the dual, because some of the required computations cannot be carried out efficiently. Nonetheless, we demonstrate that this can be resolved by a method that approximates both the primal and the dual optimization coordinates, resulting in an ALP that is well-suited for constrained problems. It effectively approximates both the optimization coordinates and the feasible regions of the LPs, and thus also serves as a new method for a widely-discussed problem of dealing with exponentially many constraints, which plagues both the primal and the dual ALP formulations.

AAMAS Conference 2004 Conference Paper

Graphical Models in Local, Asymmetric Multi-Agent Markov Decision Processes

• Dmitri Dolgov
• Edmund Durfee