|
Navigation Among Movable Obstacles (NAMO)
Robots would be far more useful if they could autonomously move obstacles out of the way. Future rescue robots that save humans from disasters such as floods and earthquakes will be required to solve Navigation Among Movable Obstacles (NAMO). Traditional motion planning algorithms search for collision-free paths from the start to the goal. This is not sufficient when the flood waters have caused furniture to float and collapse, leaving no open path to the victims. Instead, the robot must quickly decide which obstacles can be moved to clear a path to the goal. It must choose where to move objects and compute valid motion plans that integrate navigation and manipulation.
Our recent work develops practical planning algorithms that take advantage of these options while simultaneously constructing more accurate models of the environment.
This project is supported by the National Science Foundation (NSF).
Publications
Journal
Mike Stilman and James Kuffner
Planning Among Movable Obstacles with Artificial Constraints
International Journal of Robotics Research.
no. 12. 2008.
This paper presents artificial constraints as a method for guiding
heuristic search in the computationally challenging domain of motion
planning among movable obstacles. The robot is permitted to manipulate
unspecified obstacles in order to create space for a path. A plan
is an ordered sequence of paths for robot motion and object
manipulation. We show that under monotone assumptions, anticipating
future manipulation paths results in constraints on both the choice of
objects and their placements at earlier stages in the plan. We present
an algorithm that uses this observation to incrementally reduce the
search space and quickly find solutions to previously unsolved classes
of movable obstacle problems. Our planner is developed for arbitrary
robot geometry and kinematics. It is presented with an implementation
for the domain of navigation among movable obstacles
@article{stilman2008planning,
title = {Planning Among Movable Obstacles with Artificial Constraints},
number = {12},
volume = {27},
pages = {1295--1307},
journal = {International Journal of Robotics Research},
author = {Mike Stilman and James Kuffner},
year = {2008}
}
Satoshi Kagami, Koichi Nishiwaki, James Kuffner, Simon Thompson, Joel Chestnutt, Mike Stilman, and Philipp Michel
Humanoid HRP2-DHRC for Autonomous and Interactive Behavior
Robotics Research.
2007.
Recently, research on humanoid-type robots has become increasingly active,
and a broad array of fundamental issues are under investigation. However,
in order to achieve a humanoid robot which can operate in human environ-
ments, not only the fundamental components themselves, but also the suc-
cessful integration of these components will be required. At present, almost
all humanoid robots that have been developed have been designed for bipedal
locomotion experiments. In order to satisfy the functional demands of loco-
motion as well as high-level behaviors, humanoid robots require good me-
chanical design, hardware, and software which can support the integration of
tactile sensing, visual perception, and motor control. Autonomous behaviors
are currently still very primitive for humanoid-type robots. It is difficult to
conduct research on high-level autonomy and intelligence in humanoids due
to the development and maintenance costs of the hardware. We believe low-
level autonomous functions will be required in order to conduct research on
higher-level autonomous behaviors for humanoids.
@article{kagami2007hrp2,
title = {Humanoid HRP2-DHRC for Autonomous and Interactive Behavior},
volume = {28},
pages = {103--117},
journal = {Robotics Research},
author = {Satoshi Kagami and Nishiwaki, Koichi and James Kuffner and Thompson, Simon and Chestnutt, Joel and Mike Stilman and Michel, Philipp},
year = {2007}
}
Mike Stilman, Koichi Nishiwaki, Satoshi Kagami, and James Kuffner
Planning and Executing Navigation Among Movable Obstacles
Springer Journal of Advanced Robotics.
no. 14. 2007.
This paper explores autonomous locomotion, reaching, grasping and
manipulation for the domain of Navigation Among Movable Obstacles
(NAMO). The robot perceives and constructs a model of an environment
filled with various fixed and movable obstacles, and automatically plans
a navigation strategy to reach a desired goal location. The planned
strategy consists of a sequence of walking and compliant manipulation
operations. It is executed by the robot with online feedback. We give
an overview of our NAMO system, as well as provide details of the
autonomous planning, online grasping and compliant hand positioning
during dynamically-stable walking. Finally, we present results of a
successful implementation running on the Humanoid Robot HRP-2.
@article{stilman2007planning,
title = {Planning and Executing Navigation Among Movable Obstacles},
number = {14},
volume = {21},
pages = {1617--1634},
journal = {Springer Journal of Advanced Robotics},
author = {Mike Stilman and Nishiwaki, Koichi and Satoshi Kagami and James Kuffner},
year = {2007}
}
Mike Stilman and James Kuffner
Navigation Among Movable Obstacles: Real-Time Reasoning in Complex Environments
International Journal on Humanoid Robotics.
no. 4. 2005.
In this paper, we address the problem of Navigation Among Movable
Obstacles (NAMO): a practical extension to navigation for humanoids
and other dexterous mobile robots. The robot is permitted to
reconfgure the environment by moving obstacles and clearing free space
for a path. This paper presents a resolution complete planner for a
subclass of NAMO problems. Our planner takes advantage of the
navigational structure through state-space decomposition and heuristic
search. The planning complexity is reduced to the difficulty of the
specified navigation task, rather than the dimensionality of the
multiobject domain. We demonstrate real-time results for spaces that
contain large numbers of movable obstacles. We also present a
practical framework for single-agent search that can be used in
algorithmic reasoning about this domain.
@article{stilman2005navigation,
title = {Navigation Among Movable Obstacles: Real-Time Reasoning in Complex Environments},
number = {4},
volume = {2},
pages = {479--504},
month = {December},
journal = {International Journal on Humanoid Robotics},
author = {Mike Stilman and James Kuffner},
year = {2005}
}
Books and Chapters
Mike Stilman
Autonomous Manipulation of Movable Obstacles
Ch. 8. Ed. Kensuke Harada, Eiichi Yoshida, and Kazuhito Yokoi. University of Chicago Press. 2010.
In this chapter we describe recent progress towards autonomous manipulation
of environment objects. Many tasks, such as nursing home assistance, construction
or search and rescue, require the robot to not only avoid obstacles but also move
them out if its way to make space for reaching the goal. We present algorithms that
decide which objects should be moved, where to move them and how to move them.
Finally, we introduce a complete system that takes into account humanoid balance,
joint limits and fullbody constraints to accomplish environment interaction.
@inbook{stilman2010mphr,
title = {Autonomous Manipulation of Movable Obstacles},
publisher = {University of Chicago Press},
chapter = {8},
edition = {13},
editor = {Kensuke Harada and Eiichi Yoshida and Kazuhito Yokoi},
author = {Mike Stilman},
year = {2010}
}
Conference
- 2014
Martin Levihn, Koichi Nishiwaki, Satoshi Kagami, and Mike Stilman
Autonomous Environment Manipulation to Assist Humanoid Locomotion
IEEE International Conference on Robotics and Automation.
2014.
Legged robots have unique capabilities to traverse complex environments by stepping over and onto objects. Many footstep planners have been developed to take advantage of these capabilities. However, legged robots also have inherent constraints such as a maximum step height and distance. These constraints typically limit their reachable space, independent of footstep planning. Thus, we propose that robots such as humanoid robots that have manipulation capabilities should use them. A robot should autonomously modify its environment if necessary. We present a system that enabled a real robot to use a box to create itself a stair step or place a board on the ground to cross a gap, allowing it to reach its otherwise unreachable goal configuration.
@inproceedings{levihn2014ICRA,
title = {Autonomous Environment Manipulation to Assist Humanoid Locomotion},
booktitle = {IEEE International Conference on Robotics and Automation},
author = {Martin Levihn and Nishiwaki, Koichi and Kagami, Satoshi and Mike Stilman},
year = {2014}
}
- 2013
Jonathan Scholz, Martin Levihn, and Charles L. Isbell
What Does Physics Bias: A Comparison of Model Priors for Robot Manipulation
1st Multidisciplinary Conference on Reinforcement Learning and Decision Making.
2013.
We explore robot object manipulation as a Bayesian model-based reinforcement learning problem under a collection
of different model priors. Our main contribution is to highlight the limitations of classical non-parametric regression
approaches in the context of online learning, and to introduce an alternative approach based on monolithic physical
inference. The primary motivation for this line of research is to incorporate physical system identification into the RL
model, where it can be integrated with modern approaches to Bayesian structure learning. Overall, our results support
the idea that modern physical simulation tools provide a model space with an appropriate inductive bias for manipulation
problems in natural environments.
@inproceedings{scholz2013RLDM,
title = {What Does Physics Bias: A Comparison of Model Priors for Robot Manipulation},
booktitle = {1st Multidisciplinary Conference on Reinforcement Learning and Decision Making},
author = {Jonathan Scholz and Martin Levihn and Isbell, Charles L.},
year = {2013}
}
Martin Levihn, Matthew Dutton, Alexander Trevor, and Mike Stilman
Detecting Partially Occluded Objects via Segmentation and Validation
IEEE Workshop on Robot Vision (WoRV).
2013.
This paper presents a novel algorithm: Verfied
Partial Object Detector (VPOD) for accurate detection of
partially occluded objects such as furniture in 3D point clouds.
VPOD is implemented and validated on real sensor data
obtained by our robot. It extends Viewpoint Feature Histograms
(VFH) which classify unoccluded objects to also classifying
partially occluded objects such as furniture that might be seen
in typical office environments. To achieve this result, VPOD
employs two strategies. First, object models are segmented
and the object database is extended to include partial models.
Second, once a matching partial object is detected, the complete
object model is aligned back into the scene and verified for
consistency with the point cloud data. Overall, our approach
increases the number of objects found and substantially reduces
false positives due to the verification process.
@inproceedings{levihn2013worv,
title = {Detecting Partially Occluded Objects via Segmentation and Validation},
booktitle = {IEEE Workshop on Robot Vision (WoRV)},
author = {Martin Levihn and Dutton, Matthew and Trevor, Alexander and Mike Stilman},
year = {2013}
}
- 2012
Martin Levihn, Jonathan Scholz, and Mike Stilman
Hierarchical Decision Theoretic Planning for Navigation Among Movable Obstacles
Workshop on the Algorithmic Foundations of Robotics.
2012.
In this paper we present the first decision theoretic planner for the
problem of Navigation Among Movable Obstacles (NAMO). While efficient
planners for NAMO exist, they are challenging to implement in practice
due to the inherent uncertainty in both perception and control of real
robots. Generalizing existing NAMO planners to nondeterministic
domains is particularly difficult due to the sensitivity of MDP
methods to task dimensionality. Our work addresses this challenge by
combining ideas from Hierarchical Reinforcement Learning with Monte
Carlo Tree Search, and results in an algorithm that can be used for
fast online planning in uncertain environments. We evaluate our
algorithm in simulation, and provide a theoretical argument for our
results which suggest linear time complexity in the number of
obstacles for typical environments.
@inproceedings{levihn2012hierarchical,
title = {Hierarchical Decision Theoretic Planning for Navigation Among Movable Obstacles},
pages = {19--35},
month = {June},
booktitle = {Workshop on the Algorithmic Foundations of Robotics},
author = {Martin Levihn and Jonathan Scholz and Mike Stilman},
year = {2012}
}
- 2011
Akansel Cosgun, Tucker Hermans, Victor Emeli, and Mike Stilman
Push Planning for Object Placement on Cluttered Table Surfaces
IEEE/RSJ International Conference on Intelligent Robots and Systems.
2011.
We present a novel planning algorithm for the problem of placing
objects on a cluttered surface such as a table, counter or floor. The
planner (1) selects a placement for the target object and (2)
constructs a sequence of manipulation actions that create space for
the object. When no continuous space is large enough for direct
placement, the planner leverages means-end analysis and dynamic
simulation to find a sequence of linear pushes that clears the
necessary space. Our heuristic for determining candidate placement
poses for the target object is used to guide the manipulation
search. We show successful results for our algorithm in simulation
@inproceedings{cosgun2011push,
title = {Push Planning for Object Placement on Cluttered Table Surfaces},
pages = {4627--4632},
month = {September},
booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems},
author = {Cosgun, Akansel and Tucker Hermans and Emeli, Victor and Mike Stilman},
year = {2011}
}
- 2010
Hai-Ning Wu, Martin Levihn, and Mike Stilman
Navigation Among Movable Obstacles in Unknown Environments
IEEE/RSJ International Conference on Intelligent Robots and Systems.
2010.
This paper explores the Navigation Among Movable Obstacles (NAMO)
problem in an unknown environment. We consider the realistic scenario
in which the robot has to navigate to a goal position in an unknown
environment consisting of static and movable objects. The robot may
move objects if the goal can not be reached otherwise or if moving the
object may significantly shorten the path to the goal. We consider
real situations in which the robot only has limited sensing
information and where the action selection can therefore only be based
on partial knowledge learned from the environment at that point. This
paper introduces an algorithm that significantly reduces the necessary
calculations to accomplish this task compared to a direct approach. We
present an efficient implementation for the case of planar,
axis-aligned environments and report experimental results on
challenging scenarios with more than 50 objects
@inproceedings{wu2010navigation,
title = {Navigation Among Movable Obstacles in Unknown Environments},
pages = {1433--1438},
month = {October},
booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems},
author = {Wu, Hai-Ning and Martin Levihn and Mike Stilman},
year = {2010}
}
- 2008
Jur van den Berg, Mike Stilman, James Kuffner, Ming Lin, and Dinesh Manocha
Path Planning Among Movable Obstacles: A Probabilistically Complete Approach
Workshop on the Algorithmic Foundation of Robotics.
2008.
In this paper we study the problem of path planning among movable
obstacles, in which a robot is allowed to move the obstacles if they
block the robot's way from a start to a goal position. We make the
observation that we can decouple the computations of the robot motions
and the obstacle movements, and present a probabilistically complete
algorithm, something which to date has not been achieved for this
problem. Our algorithm maintains an explicit representation of the
robot's configuration space. We present an eficient implementation for
the case of planar, axis-aligned environments and report experimental
results on challenging scenarios
@inproceedings{vandenberg2008path,
title = {Path Planning Among Movable Obstacles: A Probabilistically Complete Approach},
pages = {599--614},
month = {December},
booktitle = {Workshop on the Algorithmic Foundation of Robotics},
author = {Jur van den Berg and Mike Stilman and James Kuffner and Lin, Ming and Manocha, Dinesh},
year = {2008}
}
- 2007
Mike Stilman, Jan-Ullrich Schamburek, James Kuffner, and Tamim Asfour
Manipulation planning among movable obstacles
IEEE International Conference on Robotics and Automation.
2007.
This paper presents the ResolveSpatialConstraints (RSC) algorithm for
manipulation planning in a domain with movable obstacles. Empirically
we show that our algorithm quickly generates plans for simulated
articulated robots in a highly nonlinear search space of exponential
dimension. RSC is a reverse-time search that samples future robot
actions and constrains the space of prior object displacements. To
optimize the efficiency of RSC, we identify methods for sampling object
surfaces and generating connecting paths between grasps and
placements. In addition to experimental analysis of RSC, this paper
looks into object placements and task-space motion constraints among
other unique features of the three dimensional manipulation planning
domain.
@inproceedings{stilman2007manipulation,
title = {Manipulation planning among movable obstacles},
pages = {3327--3332},
month = {April},
booktitle = {IEEE International Conference on Robotics and Automation},
author = {Mike Stilman and Schamburek, Jan-Ullrich and James Kuffner and Tamim Asfour},
year = {2007}
}
Mike Stilman
Task Constrained Motion Planning in Robot Joint Space
IEEE/RSJ International Conference on Intelligent Robots and Systems.
2007.
We explore global randomized joint space path planning for articulated
robots that are subject to task space constraints. This paper
describes a representation of constrained motion for joint space
planners and develops two simple and efficient methods for constrained
sampling of joint configurations: Tangent Space Sampling (TS) and
First-Order Retraction (FR). Constrained joint space planning is
important for many real world problems involving redundant
manipulators. On the one hand, tasks are designated in work space
coordinates: rotating doors about fixed axes, sliding drawers along
fixed trajectories or holding objects level during transport. On the
other, joint space planning gives alternative paths that use redundant
degrees of freedom to avoid obstacles or satisfy additional goals
while performing a task. In simulation, we demonstrate that our
methods are faster and significantly more invariant to
problem/algorithm parameters than existing techniques
@inproceedings{stilman2007task,
title = {Task Constrained Motion Planning in Robot Joint Space},
pages = {3074--3081},
month = {October},
booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems},
author = {Mike Stilman},
year = {2007}
}
- 2006
Mike Stilman, Koichi Nishiwaki, Satoshi Kagami, and James Kuffner
Planning and Executing Navigation Among Movable Obstacles
IEEE/RSJ International Conference on Intelligent Robots and Systems.
2006.
This paper explores autonomous locomotion, reaching, grasping and
manipulation for the domain of Navigation Among Movable Obstacles
(NAMO). The robot perceives and constructs a model of an environment
filled with various fixed and movable obstacles, and automatically plans
a navigation strategy to reach a desired goal location. The planned
strategy consists of a sequence of walking and compliant manipulation
operations. It is executed by the robot with online feedback. We give
an overview of our NAMO system, as well as provide details of the
autonomous planning, online grasping and compliant hand positioning
during dynamically-stable walking. Finally, we present results of a
successful implementation running on the Humanoid Robot HRP-2
@inproceedings{stlman2006planning,
title = {Planning and Executing Navigation Among Movable Obstacles},
pages = {1617--1634},
month = {October},
booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems},
author = {Mike Stilman and Nishiwaki, Koichi and Satoshi Kagami and James Kuffner},
year = {2006}
}
Mike Stilman and James Kuffner
Planning Among Movable Obstacles with Artificial Constraints
Workshop on the Algorithmic Foundations of Robotics.
2006.
This paper presents artiificial constraints as a method for guiding
heuristic search in the computationally challenging domain of motion
planning among movable obstacles. The robot is permitted to manipulate
unspecifieed obstacles in order to create space for a path. A plan is an
ordered sequence of paths for robot motion and object manipulation. We
show that under monotone assumptions, anticipating future manipulation
paths results in constraints on both the choice of objects and their
placements at earlier stages in the plan. We present an algorithm that
uses this observation to incrementally reduce the search space and
quickly find solutions to previously unsolved classes of movable
obstacle problems. Our planner is developed for arbitrary robot
geometry and kinematics. It is presented with an implementation for
the domain of navigation among movable obstacles.
@inproceedings{stilman2006planningamong,
title = {Planning Among Movable Obstacles with Artificial Constraints},
pages = {1295--1307},
month = {July},
booktitle = {Workshop on the Algorithmic Foundations of Robotics},
author = {Mike Stilman and James Kuffner},
year = {2006}
}
- 2004
Mike Stilman and James Kuffner
Navigation Among Movable Obstacles: Real-time Reasoning in Complex Environments
IEEE/RAS International Conference on Humanoid Robotics.
2004.
In this paper, we address the problem of Navigation Among Movable
Obstacles (NAMO): a practical extension to navigation for humanoids
and other dexterous mobile robots. The robot is permitted to
reconfigure the environment by moving obstacles and clearing free
space for a path. This paper presents a resolution complete planner
for a subclass of NAMO problems. Our planner takes advantage of the
navigational structure through state-space decomposition and heuristic
search. The planning complexity is reduced to the difficulty of the
specific navigation task, rather than the dimensionality of the
multiobject domain. We demonstrate real-time results for spaces that
contain large numbers of movable obstacles. We also present a
practical framework for single-agent search that can be used in
algorithmic reasoning about this domain.
@inproceedings{stilman2004navigation,
title = {Navigation Among Movable Obstacles: Real-time Reasoning in Complex Environments},
pages = {322--341},
month = {November},
booktitle = {IEEE/RAS International Conference on Humanoid Robotics},
author = {Mike Stilman and James Kuffner},
year = {2004}
}
Workshop
Victor Emeli, Charlie Kemp, and Mike Stilman
Push Planning for Object Placement in Clutter Using the PR-2.
The PR2 Workshop, IEEE Int. Conf. on Intelligent Robots and Systems.
2011.
The goal of this project is to investigate the implementation of a
planning algorithm for the problem of placing objects on a cluttered
surface with a PR-2 mobile manipulator. The original push planning
algorithm was initially developed as a simulation. We modified the
simulator for execution in real-world cluttered environments. This
paper discusses the challenges of implementation and presents
empirical results that determine how well the simulator models the
real world as clutter is pushed and collides with other objects
@inproceedings{emeli2011push,
title = {Push Planning for Object Placement in Clutter Using the PR-2.},
month = {September},
booktitle = {The PR2 Workshop, IEEE Int. Conf. on Intelligent Robots and Systems},
author = {Emeli, Victor and Charlie Kemp and Mike Stilman},
year = {2011}
}
Technical Reports
Martin Levihn, Matthew Dutton, Alexander Trevor, and Mike Stilman
Detecting Partially Occluded Objects via Segmentation and Validation
no. GT-GOLEM-2012-001. Georgia Institute of Technology, Atlanta, GA. 2012.
This paper presents a novel algorithm: Verfied Partial Object Detector
(VPOD) for accurate detection of partially occluded objects such as
furniture in 3D point clouds. VPOD is implemented and validated on
real sensor data obtained by our robot. It extends Viewpoint Feature
Histograms (VFH) which classify unoccluded objects to also classifying
partially occluded objects such as furniture that might be seen in
typical office environments. To achieve this result, VPOD employs two
strategies. First, object models are segmented and the object database
is extended to include partial models. Second, once a matching
partial object is detected, the full object model is aligned back into
the scene and verified for consistency with the point cloud
data. Overall, our approach increases the number of objects found and
substantially reduces false positives due to the verification process.
@techreport{levihn2012detecting,
title = {Detecting Partially Occluded Objects via Segmentation and Validation},
number = {GT-GOLEM-2012-001},
institution = {Georgia Institute of Technology, Atlanta, GA},
author = {Martin Levihn and Dutton, Matthew and Alexander Trevor and Mike Stilman},
year = {2012}
}
Martin Levihn and Mike Stilman
Efficient Opening Detection
no. GT-GOLEM-2011-002. Georgia Institute of Technology. 2011.
We present an efficient and powerful algorithm for detecting openings.
Openings indicate the existence of a new path for the robot. The reliable
detection of new openings is of great relevance for the domain of moving
objects as a robot typically needs to detect openings for itself to navigate
through. It is also especially relevant to the domain of Navigation Among
Movable Obstacles in known as well as unknown environments. In these domains
a robot has to plan for object manipulations that help it to navigate to the
goal. Tremendous speed-ups for algorithms in these domains can be achieved by
limiting the considerations of obstacle manipulations to cases where
manipulations create new openings. The presented algorithm can detect openings
for obstacles of arbitrary shapes being displaced or moving by themselves, in
arbitrarily directions in changing environments. To the knowledge of the
authors, this is the first algorithm to achieve efficient opening detection
for arbitrary shaped obstacles.
@techreport{levihn2011efficient,
title = {Efficient Opening Detection},
number = {GT-GOLEM-2011-002},
institution = {Georgia Institute of Technology},
author = {Martin Levihn and Mike Stilman},
year = {2011}
}
Project Members
|
|
BibTeX
PDF
