Steven M. LaValle

Biographical info (a bit personal, mixed with professional)

Click here for Chinese version (thanks to Shaoxiong Yao)

My friends and colleagues repeatedly tell me that my decisions make no sense but seem to often work out favorably. This bio might help to explain that.

Growing up

I was born in 1968 and grew up in and around St. Louis, USA. My loving parents were often overwhelmed because I asked them questions continuously to the point of exhaustion. As a child I was inspired by the space age, with Kubrick and Clarke's 2001 exciting me with dreams of a future full of space exploration and intelligent machines (HAL 9000). No one in my family had gone to college, and nearly everyone around me was skeptical about higher education (why would you let them "educate the brains out of you?" or "After that, he ain't got no more common sense."). This made it seem nearly impossible to get on track for helping build that envisioned future. Also, while I was growing up, the space age was slowly disintegrating.

In the early 1980s, I spent much of my spare time in video arcades and on the Atari 2600 home console. It blew my mind when I heard that a kid up the street had a computer and it could be used to "program his own" video games. I quickly read a book and started programming regularly on a display TI 99/4A at Kmart. I couldn't believe that I could make this machine do whatever I wanted! Eventually, I scrounged up enough money to get the cheapest home computer (TS 1000 with 2k memory), and when I turned 16, I worked lousy food service jobs all summer to buy a Commodore 64. This allowed me write all kinds of programs, both in BASIC and machine language, with my favorite still being to make video games. At the same time, this activity, along with some inspiring teachers, gave me enough confidence to go from being a terrible student in high school to being the top student in every subject. This required a huge amount of work and determination. I think this made me not very popular among some people who came from more educated and wealthy families.

Near the end of high school, I still believed that engineers mostly drive locomotives, but my guidance counselor pointed out that with my interests in math, science, and computers, I should probably be an electrical or computer engineer. He then showed me a college guide to convince me that some school in Missouri was one of the "top" (it wasn't listed there), and I looked over his shoulder and saw the top 3 schools listed as "MIT", "Stanford", and "Illinois". He didn't seem to know anything about "Illinois", but I made it my mission to learn about it. I figured that MIT and Stanford were only for rich people from another planet, but Illinois happened to be the name of that state on the other side of the Mississippi River from St. Louis. I soon realized that "Illinois" was UIUC, which was actually the home of the fictional HAL 9000 Computer from 2001! It was to be completed in 1992 (movie) or 1997 (book), which meant I had a chance to help realize at least part of the glorious future of that movie. It took me a couple of years of complicated scheming to borrow money in every way possible to cover the triple out-of-state tuition rate. When I finally figured it out, I had to personally petition to UIUC Engineering Dean to even be allowed to apply as an out-of-state transfer student, and they said I was the only one they let in over the past decade. Persistence! I then fought for two more years to get all prior credits transferred, and finally graduated as one of the top students from Electrical and Computer Engineering in 1989.

The reason I included the bits above is to explain why I always have strong empathy for people who have struggled because they are not part of the usual group in power. In my case, it was mostly about coming from a poorer, working-class family. Doing something smart would often lead to bullying. I could feel people having contempt for me as I succeeded and maybe even outperformed them, when based on my way of speaking, clothing, or whatever else, I should have been easily beaten. I really didn't care for competition; I just wanted to ensure I could be in a place where I could work with very smart, open-minded people. I am certain that others who struggle with additional issues based on race, gender, sexuality, disabilities, foreign nationality, and so on, face these problems and more. I had to learn how to speak and act differently to fit into the higher levels of society, but to this day I continue to have feelings of impostor syndrome. If you know what I am talking about, then please be sympathetic and support each other (and not only the ones in your own group)!

Graduate school at UIUC

Given my insatiable curiosity, a BS degree was not enough for me. The more I learned, the more I realized that there was much more to learn. In 1989, I was delighted to enter the PhD program in Electrical Engineering at UIUC, which was ranked 2 or 3 in the US at the time. The Beckman Institute was a shiny new building that seemed devoted (in my mind, at least) to making the HAL 9000 computer. I studied every form of AI in my first year of grad school, but was quickly disheartened. It seemed heavy on software (which I liked), but very weak on math and physics. (This was around 1990, and the vast majority of AI researchers had not even embraced probability theory yet, let alone interesting engineering subjects such as stochastic systems and control theory.) After my first year, I chose an inspiring new professor, Seth Hutchinson, as my PhD adviser, and I got to work at the Beckman Institute! I told him that I wanted to work on decision making under uncertainty, and spent the next couple of years working on low-level computer vision. I was buried in stochastic methods, Bayesian analysis, Monte Carlo methods, and even real analysis. I finally had enough freedom to take whatever courses I wanted, and focused heavily on pure, PhD-level mathematics, including algebra, topology, differential geometry, and analysis. This forever helped me to think better. My MS thesis work produced 3 journal papers, CVIU 95, PAMI 95, and TIP 97, and I got nice notice and positive feedback from pioneers of the day, including Ruzena Bajcsy, Azriel Rosenfeld, and David Mumford. This helped a little bit with my impostor syndrome!

My PhD adviser was horrified when halfway through my PhD I told him that I thought computer vision wasn't beautiful enough and I instead I wanted to work on robot motion planning (it was partly his fault because he was getting interested in it as well, largely due to Jean-Claude Latombe's new book). The problems in that area were specified with such perfect clarity, and they were full of video-game-like geometry that reminded me of my teenage programming years. While reading the book of Basar and Olsder on dynamic game theory, I could finally realize how to unify everything I cared about up until then: geometry, dynamical systems and control, and decision making under uncertainty. My curiosity always drives me to wonder precisely how various subjects are related. I fell in love with the notion of information spaces, which became central to much of my later work. The concept was developed in sequential game theory, and was largely introduced by von Neumann and Morgenstern (before Shannon's information theory!). This Algorithmica paper expresses that unified vision.

I strongly wanted to develop computational approaches to solve motion planning problems that involved more general challenges, beyond obstacle avoidance, such as optimality, differential constraints (control system models), prediction uncertainty, and sensing uncertainty. After spending substantial time in the engineering library, I found the right methods to build upon from Richard Bellman's dynamic programming, which came from a time when dynamic programming did not yet mean different things to computer scientists (a divide-and-conquer algorithm strategy) and electrical engineers (a differential equation that constrains optimal solutions). I figured out how to extend the numerical computation approaches of Larson and Casti from the 1960s from one dimension to multidimensional motion planning problems. This led to three main works in my PhD thesis: 1) Pareto-optimal coordination of multiple robots by extending Dijkstra's algorithm to partial orders TRA 98, 2) optimal feedback planning under sensing uncertainty IJRR 98, and 3) optimal feedback planning for hybrid systems under stochastic prediction uncertainty IJRR 97.

The funny thing about my work in graduate school is that I moved from AI to robotics because I wanted to learn and use more math, especially the real-variable kind. Most of the work I did in my thesis, though, used methods that are now commonly accepted by AI researchers. For example, reinforcement learning is mostly numerical dynamic programming (value iteration, optimal control theory). However, I was introducing this way of thinking to algorithmic roboticists and computer scientists at a time when differential equations were not attractive to them. Often times you can have the right idea, but it takes a community of people to slowly accept it, unless it is already a trend (but I find it relatively boring to target a trend). I just wanted to unify ways of thinking by people who came from different backgrounds, which eventually expanded into my Planning Algorithms book. I always feel like I have the "wrong" background and need to learn how to fit in, but once I learn how to do that for multiple cultures, I want to find ways to share the insights across the boundaries.

Postdoc at Stanford

When I graduated from UIUC in 1995 with my PhD, I had about 20 publications (a lot in those days), mostly in top places. I applied to about 60 universities for assistant professor positions, but did not get a single interview. Robotics was not popular then, and I was more motivated by discovery and understanding than marketing and popularity. My feelings of impostor syndrome worked against my ability to confidently meet people and build a social network. Fortunately, my unusual work was recognized by Prof. Jean-Claude Latombe at Stanford, who had "written the book" on my field, and he invited me to work in his group. Thus, my only professional opportunity was to be a post-doctoral researcher at Stanford, working in the most famous group in motion planning. Not bad!

The research at Stanford Computer Science pushed me into new directions. I learned about computational geometry and randomized algorithms from collaborations with Leo Guibas and Rajeev Motwani, respectively. I was funded on the final phase of a DARPA project to make one mobile robot use a camera to track and follow another one around. This led to some planning publications on maintaining visibility and visibility-based pursuit-evasion (the latter one was inspired from wondering what to do when the camera invariably lost track). One time we had to make a demo for Bill Gates, when his eponymous Stanford building was inaugurated, but it failed right before my eyes because the computer vision part had worked at 3am but not when bright California daylight had shone through the windows. In my last year there, I was moved to a Pfizer-funded project on rational drug design, and delivered software to them for finding low-energy conformations of candidate drug ligands based on pharmacophore constraints (see RECOMB 99 and JCC 00). I will never know whether they discovered any new drugs with it!

Iowa State and RRTs

After Stanford, I applied to about 80 places for assistant professor positions, and this time I got exactly one interview: Iowa State University. Thankfully, I got the job and was able to do some of my best work there.

Aside from continuing to work on pursuit-evasion (TRA 01 and IJCGA 02), my main passion was to develop a motion planning algorithm that could handle differential constraints and work in higher dimensional state spaces (more than three). I still felt that algorithmic roboticists (in computer science) thought it was trivial to connect two configurations together in the absence of obstacles (see for example, the PRM), whereas people in engineering know it as a difficult two-point boundary value problem. I had thought since 1994 that there must be a simple, efficient way to grow some kind of space-filling search tree. I could almost see it in my head, but could never find the simple algorithm that matched the mental image. Finally, while riding in the car in June 1998, I imagined that the space itself needs to pull on the tree, rather than making a heuristic based on choosing among nodes in the tree itself. I imagined that samples are generated in the whole space to taunt the tree, saying "drive toward me". Naturally, the nearest point on the tree would be the place to try to extend toward the random sample in each iteration. I excitedly coded it up that night and by midnight, I saw that it generated beautiful stochastic fractal pictures. I soon named it the RRT, for Rapidly exploring Random Tree (the name was inspired by rapidly mixing Markov chains). I quickly reconnected with my friend James Kuffner, who was a student at Stanford, and with whom we had tried unsuccessfully to collaborate before on motion planners. In the following few months, creative ideas and implementations flew back and forth, and we soon had an exciting ICRA 99 paper with a very efficient bidirectional planner, which was orders of magnitude faster than competing methods on typical benchmarks. To help in promoting our work, I made the RRT Page and the Motion Strategy Library (the first open-source library for motion planning). The RRT has been my most cited and influential contribution to research to date.

In 2019, James and I even received the first-ever IEEE ICRA Milestone Award for that paper, judged to be the most influential of all papers published at ICRA between 1997 and 2001. RRTs have been extended and used in thousands of places; the asymptotically optimal RRT* is perhaps the most notable extension, coming from Sertac Karaman's PhD thesis at MIT in 2012. Interestingly, my first two papers on RRTs were rejected, even as a short technical note, and the award-winning ICRA paper was only marginally accepted (nowhere near best-paper qualification at that time). I mention this only so that people are not deterred by early rejections or lack of interest!

Return to UIUC

After the RRT, I had gained enough popularity to look appealing to top universities. Friends at UIUC invited me to apply for a faculty position, and I was offered the chance to go back to the place where I got my PhD, which is virtually forbidden in most US universities. I was a professor there from 2001 until 2018, and was fortunate enough to work with many brilliant students and colleagues.

In terms of research there, I first began to question the foundations of randomized motion planning, in which the community seemed to believe that random sampling itself was beating the curse of dimensionality. After studying quasi-Monte Carlo literature (see this math book), I became convinced it was actually not true (see IJRR 04). Deterministic sampling is actually better than random in lower dimensions, and the two are roughly comparable in higher dimensions. It also has the advantage of being guaranteed to find a solution if one exists (when used in an appropriate planner). The only advantage of randomness seemed to be that it was easier for novices to keep from making bad mistakes. This even had implications on RRTs, and we made efforts to derandomize them (see ICRA 04 and ICRA 11). As a consequence of this general realization about the relative unimportance of random sampling in motion planning, I coined the term sampling-based motion planning, which is now in widespread use.

In 2004, I spent the entire year on sabbatical, half of which was in Poznan, Poland. I wrote a 1000-page book that unified all forms of planning, across AI, robotics, game theory, and control theory. During that period, my brain worked better than it ever will again. I could see so many technical problems so clearly. After that, the next big challenge became clear to me: How can we minimize the size or complexity of representations that robots need to solve particular tasks autonomously? In other words, can we get away with minimal amounts of sensing and construct simpler sensor fusion methods, with lower data requirements, that are successful for problems such as navigation, searching, manipulation, and patrolling?

This led to an $8 million DARPA project called SToMP that I proposed and co-led with a mathematician, Robert Ghrist. It addressed these critical foundations of robotics, largely bringing in the information space concepts that I had learned in graduate school and refined over the years for problems such as pursuit-evasion. We formed a team of over a dozen pure mathematicians and roboticists to tackle these hard problems. In the SToMP program, and a later $6 million ONR MURI project called "Reasoning in Reduced Information Spaces", we produced many new results in which the information that is sensed and used for decision making is greatly reduced in comparison to what is typically used for sensor fusion and SLAM methods in robotics. Most of the challenge was to find useful mathematical models called virtual sensors, which could have many possible physical implementations. After this, the problems live in a natural information space (or I-space), which is analogous to the configuration space (or C-space) in classical mechanics and motion planning.

After realizing that robots with minimal sensing often do not have enough information to reconstruct their state, I became interested in gently guiding or tricking simple robots to solve their problems while mostly leaving them to be unstable. This approach is inspired by dynamical billiards, and can be considered as a generalization that allows many kinds of bouncing laws. The idea is many simple motion laws lead to full coverage of the configuration space, and even ergodicity. The robots can bounce off of boundaries that are real or virtual, as induced by sensors and landmarks. This enables small amounts of sensing and control to have a large impact on the system; see the wild bodies page.

A deep dive into industry: Oculus VR and Huawei

Around 2012, I started to get the sense that robotics as a field was gradually becoming less interested in fundamental research, and many researchers were insisting that all work should be experimental and practical. Based on my background described above, I have tended to be respectful and supportive to all communities, which made this trend disheartening. On the other hand, I thought that if one was to do something very practical, then why not just build a product in industry? Otherwise, I could not see the point of being in academia. So, I gave it at try...

In September 2012, I got an email out of the blue from Jack McCauley, from a VR company that was founded two months earlier by a 19-year-old named Palmer Luckey. Oculus VR had just closed a successful Kickstarter campaign and needed to make head tracking work for the Oculus Rift in a hurry. Jack was googling for things like "quaternions" and "Euler angles" and found my Planning Algorithms book. I was just about to refer them to some industry-oriented colleagues, but contemplated my family financial worries, including paying for my eventual children's university tuition, retirement funds, and rising medical costs. I naively thought a successful startup could fix that. Before too long, I was their chief scientist, where I developed patented tracking technology for consumer virtual reality, and led a team of perceptual psychologists to provide principled approaches to virtual reality system calibration, health and safety, and the design of comfortable user experiences. By March 2014, Facebook agreed to buy the company for $3 billion. I guess I was lucky in my first industry experience! The overall story is nicely told in this book by Blake Harris.

The unbelievable Oculus success also opened many doors, and I had the opportunity to get to know people I never would have met before, including CEOs, venture capitalists, serial entrepreneurs, billionaires, politicians, and Hollywood people. At the same time, I returned to UIUC to continue my tenured position. I was so excited about the consumer VR revolution that I started a new course and wrote a VR book based on it. The key insight was that understanding human perception and physiology is critical to engineering of VR systems and experiences. Thus, the course and book provide a unique integration of these subjects. A version of the course was recorded by NPTEL when I visited IIT Madras in 2015 and is available online.

In 2016, I was approached by Huawei to be their Chief Scientist and Vice President for VR/AR/MR consumer products. I proposed building a big research center, in the UIUC Research Park, which would be a joint effort between the University of Illinois and Huawei. Both parties were excited, and after a year of preparation, I joined Huawei while retaining a part-time UIUC position. Like many US universities, UIUC had taken in many thousands of high-paying Chinese students in recent years (presumably to help with rising costs and the lack of tax funding). These students were absolutely shocked and thrilled that I was leading this effort, bridging the gaps between China and the US. Needless to say this was eventually doomed in 2017 amid rising nationalism, the eventual US-China trade war, and Huawei being put on the entity list. I nevertheless had a wonderful time working in Huawei and learned so much about consumer product development. I met many hard working, kind, and intellectually interesting people, and thoroughly enjoyed the culture in Shenzhen, Shanghai, and Hangzhou.

After the industry experiences, I could see startling differences between the academic and business worlds. I was most comfortable in universities, where I was able to freely learn, grow, and openly share whatever I know with people around me. In industry, information is protected, which leads to complicated games and strategies for gaining power based on who knows what. It is a difficult place to be if you enjoy sharing your knowledge and understanding, and generally helping people with their projects. I also found the Dunning-Kruger effect to cause serious problems in industry, especially when people don't know what they don't know, but have massive power over others and company directions. Both worlds clearly play important roles, but I learned that a university research environment makes me the happiest. I feel very lucky to have been able to try both at fairly high levels.

Moving to Finland

One "occupational hazard" of being a professor is exposure to various countries, cultures, and people from all over the world. I was very fortunate to visit a few dozen countries, often hosted by people who have the same professional interests. This made me wonder what my life would be like if I had grown up there. I became attracted to Poland, where I have family heritage, and then Nordic countries. I was especially attached to Finland after teaching a short course at the University of Vaasa in 2007; I was invited by Pekka Isto, a Finnish motion planning expert.

In 2012-2013, I brought my family to Oulu for a sabbatical to write books and get to know Finland better. After living there for nine months, we came to deeply appreciate Finnish culture and lifestyle. It seemed that Finland naturally fit my personality. People are respectful of each other and generally cooperate in maintaining a safe, responsible, and fair society. Modesty and respect for cultural differences around the world are strongly emphasized. Education and educators are highly respected. I thought it would be perfect for raising my children, with safe, playful, and nurturing infrastructure, and where good health care and education are free rights of residents (private universities are even illegal). Relating to my profession, there is strong interest in developing advanced technology while also being respectful of nature, the environment, and wellbeing. These are the values that suit me well, and that I want my family to learn. In 2018, I was invited to become a professor at the University of Oulu, and I could not be happier. I am currently co-leading the Perception Engineering Group, which pursues problems in virtual reality, robotics, and telepresence. The university made a nice video about me, and a Finnish newspaper explains more about why I moved to Oulu. I am also involved in helping the industrial ecosystem in Finland, especially in virtual reality and its various flavors (VR, AR, MR, XR, ...).

I look forward to many more learning adventures ahead!