Steven M. LaValle

Robot Brains and Information Spaces

To accomplish a typical task, such as cleaning a floor or patrolling a building, how much sening and internal representation does a robot need to have? This is a classic yet elusive question. At one extreme, it is enough to connect a contact sensor directly to motors, as in the case of this wall-following mouse toy. At the other extreme, complex sensors such as range scanners, cameras, and IMUs may be used to build and maintain a perfect map with perfect localization. For the vast majority of problems the ideal representation lies someone between these extremes. It is important to look for these for two reasons: 1) If an autonomous system is to ever to become a product, then it is important to elminate unnecessary components and reduce complexity so that costs and energy consumption are decreased, while reliability and maintainability are increased. 2) It provides a deep insight into the requirements of a task, ultimately helping in robot system design. This is a natural complement to the current trends in machine learning, in which highly complex representations are learned from massive data sets. We are interested in the simplest, most understandable, and analyzable solutions to problems. One of the central ideas is to use the notion of information spaces, which arose in the 1940s in the context of sequential game theory where the players cannot directly observe the game state. Similarly, a robot must made appropriate decisions without being able to fully sense and know the world around it. We called the information spaces I-spaces because they serve a similar purpose as C-spaces for robotics. For an introduction to I-spaces, see Chapter 11 of my book or the "Minimalism in Robotics" tutorial on my tutorials page.

Some highlights of our results are:



Papers on Sensing and Information Spaces

Chapter 11: Sensors and Information Spaces, Planning Algorithms. S. M. LaValle. Cambridge University Press, Cambridge, U.K., 2006. [pdf] [Entire Book].

Chapter 12: Planning Under Sensing Uncertainty, Planning Algorithms. S. M. LaValle. Cambridge University Press, Cambridge, U.K., 2006. [pdf] [Entire Book].

Virtual reality for robots. M. Suomalainen, A. Q. Nilles, and S. M. LaValle. In IEEE International Conference on Robotics and Automation, 2020. Under review, [pdf].

Sensor lattices: Structures for comparing information feedback. S. M. LaValle. In IEEE International Workshop on Robot Motion and Control, 2019. [pdf].

Combinatorial filters: Sensor beams, obstacles, and possible paths. B. Tovar, F. Cohen, L. Bobadilla, J. Czarnowski, and S. M. LaValle. ACM Transactions on Sensor Networks, 10(3), 2014. [pdf].

Intensity-based navigation with global guarantees. K. Taylor and S. M. LaValle. Autonomous Robots, 36(4):349-364, 2014. [pdf].

Exploration of an unknown environment with a differential drive disc robot. G. Laguna, R. Murrieta-Cid, H. M. Becerra, R. Lopez-Padilla, and S. M. LaValle. In IEEE International Conference on Robotics and Automation, 2014. [pdf].

Sensing and Filtering: A Fresh Perspective Based on Preimages and Information Spaces. S. M. LaValle. volume 1:4 of Foundations and Trends in Robotics Series. Now Publishers, Delft, The Netherlands, 2012. [pdf].

Counting moving bodies using sparse sensor beams. L. Erickson, J. Yu, Y. Huang, and S. M. LaValle. In Proc. Workshop on the Algorithmic Foundations of Robotics, 2012. [pdf].

Optimal gap navigation for a disc robot. R. Lopez-Padilla, R. Murrieta-Cid, and S. M. LaValle. In Proc. Workshop on the Algorithmic Foundations of Robotics, 2012. [pdf].

Navigation among visually connected sets of partially distinguishable landmarks. L. Erickson and S. M. LaValle. In IEEE International Conference on Robotics and Automation, 2012. [pdf].

Rendezvous without coordinates. J. Yu, D. Liberzon, and S. M. LaValle. IEEE Transactions on Automatic Control, 57(2):421-434, 2012. [pdf].

Shadow information spaces: Combinatorial filters for tracking targets. J. Yu and S. M. LaValle. IEEE Transactions on Robotics, 28(2):440-456, 2012. [pdf].

Sensor lattices: A preimage-based approach to comparing sensors. S. M. LaValle. September 2011. Department of Computer Science, University of Illinois, [pdf].

How many landmark colors are needed to avoid confusion in a polygon?. L. Erickson and S. M. LaValle. In IEEE International Conference on Robotics and Automation, 2011. [pdf].

Story validation and approximate path inference with a sparse network of heterogeneous sensors. J. Yu and S. M. LaValle. In IEEE International Conference on Robotics and Automation, 2011. [pdf].

An art gallery approach to ensuring that landmarks are distinguishable. L. Erickson and S. M. LaValle. In Proceedings Robotics: Science and Systems, 2011. [pdf].

Learning the Delaunay triangulation of landmarks from a distance ordering sensor. M. Katsev and S. M. LaValle. In Proceedings IEEE International Conference on Intelligent Robots and Systems, 2011. [pdf].

Minimalist multiple target tracking using directional sensor beams. L. Bobadilla, O. Sanchez, J. Czarnowski, and S. M. LaValle. In Proceedings IEEE International Conference on Intelligent Robots and Systems, 2011. [pdf].

Mapping and pursuit-evasion strategies for a simple wall-following robot. M. Katsev, A. Yershova, B. Tovar, R. Ghrist, and S. M. LaValle. IEEE Transactions on Robotics, 27(1):113-128, 2011. [pdf].

Learning combinatorial map information from permutations of landmarks. B. Tovar, L. Freda, and S. M. LaValle. International Journal of Robotics Research, 30(9):1143-1156, 2011. [pdf].

Cyber detectives: Determining when robots or people misbehave. J. Yu and S. M. LaValle. In Proceedings Workshop on Algorithmic Foundations of Robotics (WAFR), 2010. [pdf].

Searching and mapping among indistinguishable convex obstacles. B. Tovar and S. M. LaValle. In IEEE International Conference on Robotics and Automation, 2010. [pdf].

Probabilistic shadow information spaces. J. Yu and S. M. LaValle. In IEEE International Conference on Robotics and Automation, 2010. [pdf].

Filtering and planning in information spaces. S. M. LaValle. Technical report, Department of Computer Science, University of Illinois, October 2009. [pdf].

I-Bug: An intensity-based bug algorithm. K. Taylor and S. M. LaValle. In Proceedings IEEE International Conference on Robotics and Automation, 2009. [pdf].

Sensor beams, obstacles, and possible paths. B. Tovar, F. Cohen, and S. M. LaValle. In Proceedings Workshop on Algorithmic Foundations of Robotics (WAFR), 2008. [pdf].

Rendezvous without coordinates. J. Yu, D. Liberzon, and S. M. LaValle. In Proceedings IEEE Conference Decision and Control, pages 1803-1808, 2008. [pdf].

Visibility-based pursuit-evasion with bounded speed. B. Tovar and S. M. LaValle. International Journal of Robotics Research, 27(11-12):1350-1360, 2008. [pdf].

Tracking hidden agents through shadow information spaces. J. Yu and S. M. LaValle. In Proceedings IEEE International Conference on Robotics and Automation, 2008. [pdf].

Probabilistic localization with a blind robot. L. H. Erickson, J. Knuth, J. M. O'Kane, and S. M. LaValle. In Proceedings IEEE International Conference on Robotics and Automation, 2008. [pdf].

On time: Clocks, chronometers, and open-loop control. S. M. LaValle and M. B. Egerstedt. In Proceedings IEEE Conference Decision and Control, 2007. [pdf].

On comparing the power of robots. J. M. O'Kane and S. M. LaValle. International Journal of Robotics Research, 27(1):5-23, 2008. [pdf].

Using a robot to learn geometric information from permutations of landmarks. B. Tovar, L. Freda, and S. M. LaValle. In Contemporary Mathematics, volume 438, pages 33-45. American Mathematical Society, 2007. [pdf].

Distance-optimal navigation in an unknown environment without sensing distances. B. Tovar, R Murrieta-Cid, and S. M. LaValle. IEEE Transactions on Robotics, 23(3):506-518, June 2007. [pdf].

Sloppy motors, flaky sensors, and virtual dirt: Comparing imperfect, ill-informed robots. J. M. O'Kane and S. M. LaValle. In Proceedings IEEE International Conference on Robotics and Automation, 2007. [pdf].

Learning combinatorial information from alignments of landmarks. L. Freda, B. Tovar, and S. M. LaValle. In Proceedings IEEE International Conference on Robotics and Automation, 2007. [pdf].

Mapping and navigation from permutations of landmarks. B. Tovar, L. Freda, and S. M. LaValle. Technical report, Department of Computer Science, University of Illinois, June 2006. [pdf].

Visibility-based pursuit-evasion with bounded speed. B. Tovar and S. M. LaValle. In Proceedings Workshop on Algorithmic Foundations of Robotics, 2006. [pdf].

On comparing the power of mobile robots. J. M. O'Kane and S. M. LaValle. In Proceedings Robotics: Science and Systems, 2006. [pdf].

Localization with limited sensing. J. M. O'Kane and S. M. LaValle. IEEE Transactions on Robotics, 23(4):704-716, August 2007. [pdf].

Algorithms for planning under uncertainty in prediction and sensing. J. M. O'Kane, B. Tovar, P. Cheng, and S. M. LaValle. In Autonomous Mobile Robots: Sensing, Control, Decision-Making, and Applications. Marcel Dekker, 2006. [pdf].

Clearing a polygon with two 1-searchers. B. Simov, G. Slutzki, and S. M. LaValle. International Journal of Computational Geometry and Applications, 19(1), 2009. [pdf].

Information spaces for mobile robots. B. Tovar, A. Yershova, J. M. O'Kane, and S. M. LaValle. In Proceedings International Workshop on Robot Motion and Control (RoMoCo 2005), 2005. [pdf].

Bitbots: Simple robots solving complex tasks. A. Yershova, B. Tovar, R. Ghrist, and S. M. LaValle. In Proceedings AAAI National Conference on Artificial Intelligence, 2005. [pdf].

Almost-sensorless localization. J. M. O'Kane and S. M. LaValle. In Proceedings IEEE International Conference on Robotics and Automation, 2005. [pdf].

Pursuit-evasion in an unknown environment using gap navigation trees. L. Guilamo, B. Tovar, and S. M. LaValle. In Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems, 2004. [pdf].

Visibility-based pursuit-evasion in an unknown planar environment. S. Sachs, S. Rajko, and S. M. LaValle. International Journal of Robotics Research, 23(1):3-26, January 2004. [pdf].

Gap navigation trees: A minimal representation for visibility-based tasks. B. Tovar, L. Guilamo, and S. M. LaValle. In M. Erdmann, D. Hsu, M. Overmars, and A. F. van der Stappen, editors, Algorithmic Foundations of Robotics, VI. Springer-Verlag, Berlin, 2005. [pdf].

Locally optimal navigation in multiply-connected environments without geometric maps. B. Tovar, S. M. LaValle, and R. Murrieta-Cid. In Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems, 2003. [pdf].

Optimal navigation and object finding without geometric maps or localization. B. Tovar, S. M. LaValle, and R. Murrieta-Cid. In Proceedings IEEE International Conference on Robotics and Automation, pages 464-470, 2003. [pdf].

An algorithm for searching a polygonal region with a flashlight. S. M. LaValle, B. Simov, and G. Slutzki. International Journal of Computational Geometry and Applications, 12(1-2):87-113, 2002. [pdf].

A complete pursuit-evasion algorithm for two pursuers using beam detection. B. Simov, S. M. LaValle, and G. Slutzki. In Proceedings IEEE International Conference on Robotics and Automation, pages 618-623, 2002. [pdf].

Visibility-based pursuit-evasion: The case of curved environments. S. M. LaValle and J. Hinrichsen. IEEE Transactions on Robotics and Automation, 17(2):196-201, April 2001. [pdf].

A pursuit-evasion bug algorithm. S. Rajko and S. M. LaValle. In Proceedings IEEE International Conference on Robotics and Automation, pages 1954-1960, 2001. [pdf].

Robot motion planning: A game-theoretic foundation. S. M. LaValle. Algorithmica, 26(3):430-465, 2000. [pdf].

An algorithm for searching a polygonal region with a flashlight. S. M. LaValle, B. Simov, and G. Slutzki. In Proceedings ACM Annual Symposium on Computational Geometry, 2000. [pdf].

Pursuit-evasion using beam detection. B. Simov, G. Slutzki, and S. M. LaValle. In Proceedings IEEE International Conference on Robotics and Automation, 2000. [pdf].

Visibility-based pursuit-evasion in a polygonal environment. L. J. Guibas, J.-C. Latombe, S. M. LaValle, D. Lin, and R. Motwani. International Journal of Computational Geometry and Applications, 9(5):471-494, 1999. [pdf].

Visibility-based pursuit-evasion: An extension to curved environments. S. M. LaValle and J. Hinrichsen. In Proceedings IEEE International Conference on Robotics and Automation, pages 1677-1682, 1999. [pdf].

An objective-based framework for motion planning under sensing and control uncertainties. S. M. LaValle and S. A. Hutchinson. International Journal of Robotics Research, 17(1):19-42, January 1998. [pdf].

Visibility-based pursuit-evasion in a polygonal environment. L. J. Guibas, J.-C. Latombe, S. M. LaValle, D. Lin, and R. Motwani. In F. Dehne, A. Rau-Chaplin, J.-R. Sack, and R. Tamassia, editors, WADS '97 Algorithms and Data Structures (Lecture Notes in Computer Science, 1272), pages 17-30. Springer-Verlag, Berlin, 1997. [pdf].

Robot motion planning: A game-theoretic foundation. S. M. LaValle. In J.-P. Laumond and M. Overmars, editors, Algorithms for Robotic Motion and Manipulation, pages 15-29. A K Peters, Wellesley, MA, 1997. [pdf].

Finding an unpredictable target in a workspace with obstacles. S. M. LaValle, D. Lin, L. J. Guibas, J.-C. Latombe, and R. Motwani. In Proceedings IEEE International Conference on Robotics and Automation, pages 737-742, 1997. [pdf].

Evaluating motion strategies under nondeterministic or probabilistic uncertainties in sensing and control. S. M. LaValle and S. A. Hutchinson. In Proceedings IEEE International Conference on Robotics and Automation, pages 3034-3039, April 1996. [pdf].

A game-theoretic framework for robot motion planning. S. M. LaValle. PhD thesis, University of Illinois, Urbana-Champaign, USA, July 1995. [pdf].

An objective-based stochastic framework for manipulation planning. S. M. LaValle and S. A. Hutchinson. In Proceedings IEEE/RSJ/GI International Conference on Intelligent Robots and Systems, pages 1772-1779, September 1994. [pdf].

Game theory as a unifying structure for a variety of robot tasks. S. M. LaValle and S. A. Hutchinson. In Proceedings IEEE International Symposium on Intelligent Control, pages 429-434, August 1993. [pdf].