Robot Brains and Information Spaces
To accomplish a typical task, such as cleaning a floor or patrolling
a building, how much sensing 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
somewhere 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:
- A unifying theory that establishes the existence and unique of minimal robot "brians" in a very general setting (mainly abstract set theory). Thus, the quest is on for each task or set of tasks, to find the smallest possible information transition system that solves it. This has implications at the heart of planning and machine learning, as it expresses the ideal limits, below which solutions are impossible (IJRR 23 and FNR 22).
- A new category of sensor fusion methods called combinatorial filtering, which have substantially reduced sensing requirements and computational burden. See the Simpler Sensor Fusion page for more.
- Nearly brainless robots that achieve tasks from simple bouncing laws and small amounts of occasional sensor feedback. See the Wild Bodies page for more.
- A general method to compare the power of robot systems based on whether one has at least as much I-space reachability as the other (IJRR 07). This is similar to simulation in theoretical computer science.
- Providing a navigation strategy with provable guarantees to succeed, even though the robot has no map and uses only the gradient of an energy source to determine its motions (AuRo 14). This is the most minimal, in terms of sensing capabilities, among "bug algorithms" in robotics.
- Showing that optimal robot navigation can be solved, in terms of the shortest possible distance traveled, even if the environment is unknown and the robot sensors are unable to measure distances (TRO 07)!
- Controlling multiple vehicles to rendezvous by each loosely observing the general direction of others, without any ability to measure Cartesian coordinates (TAC 07).
- Navigation and mapping using only the sensed permution of landmarks that surround the robot (IJRR 10).
- Reconsidering the terms "open loop" and "closed loop" control by investigating information states that arise from both state and time uncertainty (CDC 07). What is classically called open-loop control is actually perfect time feedback!
Papers on Sensing and Information Spaces
Equivalent environments and covering spaces for robots. V. Weinstein and S. M. LaValle. In M. Farber and J. Gonzalez, editors, Topology, Geometry and AI. EMS Series in Industrial and Applied Mathematics, 2024. In press, [pdf].
A mathematical characterization of minimally sufficient robot brains. B. Sakcak, K. G. Timperi, V. Weinstein, and S. M. LaValle. The International Journal of Robotics Research, 2023. [pdf].
Sensor localization by few distance measurements via the intersection of implicit manifolds. M. M. Bilevich, S. M. LaValle, and D. Halperin. In IEEE International Conference on Robotics and Automation, 2023. [pdf].
The limits of learning and planning: Minimal sufficient information transition systems. B. Sakcak, V. Weinstein, and S. M. LaValle. In S. M. LaValle, J. M. O'Kane, M. Otte, D. Sadigh, and P. Tokekar, editors, Algorithmic Foundations of Robotics, XV. Springer-Verlag, Berlin, 2023. [pdf].
An enactivist-inspired mathematical model of cognition. V. Weinstein, B. Sakcak, and S. M. LaValle. Frontiers in Neurorobotics, September 2022. [pdf].
Localization with few distance measurements. D. Halperin, S. M. LaValle, and B. Ugav. arXiv preprint arXiv:2209.04838, September 2022, [pdf].
Visibility-inspired models of touch sensors for navigation. K. Tiwari, B. Sakcak, P. Routray, Manivannan M., and S. M. LaValle. In IEEE/RSJ International Conference on Intelligent Robots and Systems, 2022. [pdf].
Information requirements of collision-based micromanipulation. A. Q. Nilles, A. Pervan, T. A. Berrueta, T. D. Murphey, and S. M. LaValle. In S. M. LaValle, M. Lin, T. Ojala, D. Shell, and J. Yu, editors, Algorithmic Foundations of Robotics, XIV. Springer-Verlag, Berlin, 2021. [pdf].
Virtual reality for robots. M. Suomalainen, A. Q. Nilles, and S. M. LaValle. In IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 11458-11465, 2020. [pdf].
Sensor lattices: Structures for comparing information feedback. S. M. LaValle. In Proc. IEEE/IFAC 12th International Workshop on Robot Motion and Control, pages 239-246, 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].
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].
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].
Comparing the power of robots. J. M. O'Kane and S. M. LaValle. The 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].
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].
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].