Steven M. LaValle

Wild Bodies and Erdogic Systems

This line of work pushes the extreme limits of minimalism (perhaps think of it as postmodern robotics). Heavy inspiration is taken from dynamical billiards, mostly studied in Russian mathematics, and their surprising ergodic properties. The idea is to give very simple boundary interaction laws to robots and show their power to solve problems that most people believe would require much more complicated robots.

For starters, take a weaselball (valued at about $4 US) and remove the weasel. See how well it explores. Nice behavior, but we then want to coerce them into doing something useful; therefore, we divide their environment into a discrete set of regions and design gateways that act as turnstiles to gently guide their flow. Thus, we are introducing a bit of programming into the environment itself. It is like a robotics version of Maxwell's demon. With a few pieces of paper and some bricks, we obtained one of the cheapest multi-robot coordination demos ever. This later one controls 50 robots. The next step is to design slightly more sophisticated gates. We have pliant gates, which passively control the directional flow, and actuated gates, which require energy to send the robot on its desired course. Finally, the entire concept of gates can be abstracted into a virtual gates, which achieve the same result as a physical gate, but operate via simple sensor tricks. We have also considered various robot platforms, including simple differential drive robots, Hexbug Nanos, swimming weaselballs, and even crickets (which were not harmed). This overall approach solves problems such as exploration, coverage, searching, and patrolling, even though there is very little sensing, mechanical models, or environment models. These kinds of solutions may be useful for micro and nano robots, where robots are required to be simpler and less directly controllable.

In addition to building systems, we have studied deep questions closely related to ergodicity. The key property we want is wildness which means that a body will move on a trajectory that nontangentially strikes every open set along the boundary of whatever region it is placed. The particular system model is not important.

Regarding publications below, we first considered physical gates, in RoMoCo 11 and RSS 11. Virtual gates came slightly later, in ACC 12. To design and analyze systems based on bouncing laws, visibility computations become important; see our introduction of visibility-based methods for calculating flows of bouncing robots (WAFR 18).

Go here for many more videos.


Papers on Wild Bodies and Ergodic Systems

Information requirements of collision-based micromanipulation. A. Q. Nilles, A. Pervan, T. A. Berrueta, T. D. Murphey, and S. M. LaValle. In Proc. Workshop on the Algorithmic Foundations of Robotics, 2020. [pdf].

Robust combinatorial planning over simple boundary interactions. A. Q. Nilles and S. M. LaValle. In Workshop on Robust Task and Motion Planning at Robotic Science and Systems (RSS) Conference, 2019. [pdf].

A visibility-based approach to computing nondeterministic bouncing strategies. A. Q. Nilles, Y. Ren, I. Becerra, and S. M. LaValle. In Proc. Workshop on the Algorithmic Foundations of Robotics, 2018. [pdf].

Periodic trajectories of mobile robots. A. Q. Nilles, I. Becerra, and S. M. LaValle. In Proceedings IEEE International Conference on Intelligent Robots and Systems, 2017. [pdf].

Counting moving bodies using sparse sensor beams. L. E. Erickson, J. Yu, Y. Huang, and S. M. LaValle. IEEE Transactions on Automation Science and Engineering, 10(4):853-861, 2014. [pdf].

Stochastic modeling, control, and evaluation of wild bodies. D. E. Gierl, L. Bobadilla, O. Sanchez, and S. M. LaValle. In IEEE International Conference on Robotics and Automation, 2014. [pdf].

Toward the design and analysis of blind, bouncing robots. L. H. Erickson and S. M. LaValle. In IEEE International Conference on Robotics and Automation, 2013. [pdf].

Controlling wild bodies using discrete transition systems. L. Bobadilla, O. Sanchez, J. Czarnowski, K. Gossman, and S. M. LaValle. 2012. Unpublished manuscript, [pdf].

Controlling wild mobile robots using virtual gates and discrete transitions. L. Bobadilla, F. Martinez, E. Gobst, K. Gossman, and S. M. LaValle. In Proc. American Control Conference, 2012. [pdf].

Controlling wild bodies using linear temporal logic. L. Bobadilla, O. Sanchez, J. Czarnowski, K. Gossman, and S. M. LaValle. In Proceedings Robotics: Science and Systems, 2011. [pdf].

Manipulating ergodic bodies through gentle guidance. L. Bobadilla, K. Gossman, and S. M. LaValle. In Proceedings IEEE Conference on Robot Motion and Control, 2011. [pdf].