DETERMINISTIC SAMPLING FOR MOTION PLANNING






Deterministic sampling strategies provide resolution completeness guarantees to motion planning algorithms. These guarantees come at a price. Development of deterministic sequences for most of the configuration spaces arising in motion planning is a challenging problem. The standard requirements that we put on generated samples are uniformity and incremental quality.

SOFTWARE:

Library for Uniform Deterministic Sequences/Sets of Samples over 2-sphere and SO(3)

PUBLICATIONS:

Generating Uniform Incremental Grids on SO(3) Using the Hopf Fibration
Anna Yershova, Swati Jain, Steven M. LaValle, and Julie C. Mitchell,
International Journal of Robotics Research, IJRR 2009, in print

Generating Uniform Incremental Grids on SO(3) Using the Hopf Fibration
Anna Yershova, Steven M. LaValle, and Julie C. Mitchell,
In Proc. Eighth International Workshop on the Algorithmic Foundations of Robotics (WAFR 2008) (slides)

Incremental Grid Sampling Strategies in Robotics
Stephen R. Lindemann, Anna Yershova, and Steven M. LaValle,
In Proc. Sixth International Workshop on the Algorithmic Foundations of Robotics (WAFR 2004)

Deterministic sampling methods for spheres and SO(3)
Anna Yershova and Steven M. LaValle,
In Proc. IEEE International Conference on Robotics and Automation (ICRA 2004) (slides)



MOTION PLANNING




movie



movie




Motion planning algorithms have solved many difficult problems in recent years. However, new applications bring new challenges to the most efficient algorithms in the field. This work is aimed at scaling up the efficiency of motion planning algorithms to the applications in automotive industry, computational biology, manipulation planning and others.

SOFTWARE:

MPNN: Nearest Neighbor Library for Motion Planning

PUBLICATIONS:

Improving Motion Planning Algorithms by Efficient Nearest-Neighbor Searching
Anna Yershova and Steven M. LaValle,
IEEE Transactions on Robotics, 23(1):151-157, February 2007

Motion Planning in Highly Constrained Spaces
Anna Yershova and Steven M. LaValle,
In Proc. Ninth International Workshop on Robot Motion and Control (RoMoCo 2009)

Adaptive Tuning of the Sampling Domain for Dynamic-Domain RRTs
L. Jaillet, A. Yershova, S. M. LaValle and T. Simeon,
In Proc. IEEE International Conference on Intelligent Robots and Systems (IROS 2005)

Dynamic-Domain RRTs: Efficient Exploration by Controlling the Sampling Domain
A. Yershova, L. Jaillet, T. Simeon, and S. M. LaValle,
In Proc. IEEE International Conference on Robotics and Automation (ICRA 2005) ( slides)

Efficient Nearest Neighbor Searching for Motion Planning
Anna Atramentov and Steven M. LaValle,
In Proc. IEEE International Conference on Robotics and Automation (ICRA 2002) ( slides)


PLANNING IN INFORMATION SPACES




movie1.mpg
movie2.mpg

Planning for robots with sensing uncertainty is central problem in Robotics. In our work we find that it is crucial to understand the structure of the information spaces where the solution paths lie. This helps the development of task specific minimal sensor requirements for robots.

PUBLICATIONS:

Mapping and Pursuit-Evasion Strategies For a Simple Wall-Following Robot
Anna Yershova, Benjamin Tovar, Robert Ghrist, and Steven M. LaValle
submitted to IEEE Transactions on Robotics, 2009

Extracting Visibility Information by Following Walls
Anna Yershova, Benjamin Tovar, and Steven M. LaValle,
In Sandor Fekete and Rudolf Fleischer and Rolf Klein and Alejandro Lopez-Ortiz, editors,
Dagstuhl Seminar Proceedings, 06421,
Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI),
Schloss Dagstuhl, Germany, 2007. ( slides)

Information Spaces for Mobile Robots
Benjamin Tovar, Anna Yershova, Jason M. O'Kane, and Steven M. LaValle,
invited paper at Fifth International Workshop on Robot Motion and Control (RoMoCo 2005)

Bitbots: Simple Robots Solving Complex Tasks
Anna Yershova, Benjamin Tovar, Robert Ghrist, and Steven M. LaValle,
In Proc. The Twentieth National Conference on Artificial Intelligence (AAAI 2005)