Steven M. LaValle

Vadim Weinstein, Basak Sakcak, Steven M. LaValle

We formulate five basic tenets of enactivist cognitive science that we have carefully identified in the relevant literature as the main underlying principles of that philosophy. We then develop a mathematical framework to talk about cognitive systems (both artificial and natural) which complies with these enactivist tenets. In particular we pay attention that our mathematical modeling does not attribute contentful symbolic representations to the agents, and that the agent's brain, body and environment are modeled in a way that makes them an inseparable part of a greater totality. The purpose is to create a mathematical foundation for cognition which is in line with enactivism. We see two main benefits of doing so: (1) It enables enactivist ideas to be more accessible for computer scientists, AI researchers, roboticists, cognitive scientists, and psychologists, and (2) it gives the philosophers a mathematical tool which can be used to clarify their notions and help with their debates. Our main notion is that of a sensorimotor system which is a special case of a well studied notion of a transition system. We also consider related notions such as labeled transition systems and deterministic automata. We analyze a notion called sufficiency and show that it is a very good candidate for a foundational notion in the "mathematics of cognition from an enactivist perspective". We demonstrate its importance by proving a uniqueness theorem about the minimal sufficient refinements (which correspond in some sense to an optimal attunement of an organism to its environment) and by showing that sufficiency corresponds to known notions such as sufficient history information spaces. We then develop other related notions such as degree of insufficiency, universal covers, hierarchies, strategic sufficiency. In the end, we tie it all back to the enactivist tenets.

Basak Sakcak, Kalle G. Timperi, Vadim Weinstein et al.

This paper addresses the lower limits of encoding and processing the information acquired through interactions between an internal system (robot algorithms or software) and an external system (robot body and its environment) in terms of action and observation histories. Both are modeled as transition systems. We want to know the weakest internal system that is sufficient for achieving passive (filtering) and active (planning) tasks. We introduce the notion of an information transition system for the internal system which is a transition system over a space of information states that reflect a robot's or other observer's perspective based on limited sensing, memory, computation, and actuation. An information transition system is viewed as a filter and a policy or plan is viewed as a function that labels the states of this information transition system. Regardless of whether internal systems are obtained by learning algorithms, planning algorithms, or human insight, we want to know the limits of feasibility for given robot hardware and tasks. We establish, in a general setting, that minimal information transition systems exist up to reasonable equivalence assumptions, and are unique under some general conditions. We then apply the theory to generate new insights into several problems, including optimal sensor fusion/filtering, solving basic planning tasks, and finding minimal representations for modeling a system given input-output relations.

Kshitij Tiwari, Basak Sakcak, Prasanna Routray et al.

This paper introduces mathematical models of \sensors\ for mobile robots based on visibility. Serving a purpose similar to the pinhole camera model for computer vision, the introduced models are expected to provide a useful, idealized characterization of task-relevant information that can be inferred from their outputs or observations. Possible tasks include navigation, localization and mapping when a mobile robot is deployed in an unknown environment. These models allow direct comparisons to be made between traditional depth sensors, highlighting cases in which touch sensing may be interchangeable with time of flight or vision sensors, and characterizing unique advantages provided by touch sensing. The models include contact detection, compression, load bearing, and deflection. The results could serve as a basic building block for innovative touch sensor designs for mobile robot sensor fusion systems.

Aref Amiri, Basak Sakcak, Steven M. LaValle

This paper presents a framework for safe navigation of a unicycle point robot to a goal position in an environment populated with obstacles from almost any admissible state, considering input limits. We introduce a novel QP formulation to create a Cinfinity-smooth vector field with reduced total bending and total turning. Then we design an analytic, non-linear feedback controller that inherently satisfies the conditions of Nagumo's theorem, ensuring forward invariance of the safe set without requiring any online optimization. We have demonstrated that our controller, even under hard input limits, safely converges to the goal position. Simulations confirm the effectiveness of the proposed framework, resulting in a twice faster arrival time with over 50\% lower angular control effort compared to the baseline.

Jacqueline Yau, Katherine J. Mimnaugh, Evan G. Center et al.

Cybersickness poses a serious challenge for users of virtual reality (VR) technology. Consequently, there has been significant effort to track its occurrence during VR use with passive measures like brain activity recorded through electroencephalogram (EEG). To classify cybersickness accurately, including in real time, machine learning algorithms which can extract meaningful signals from the rest of the brain data will be required. However, EEG datasets are typically very small and very high in variability between participants, which makes building effective models extremely challenging. To address these concerns, we first introduce a framework for neural networks which has subject-adaptive training with calibration and interpretation for classification given limited and imbalanced EEG data. Which features the models determine are most useful can be visualized by plotting interpretability maps from integrated gradients and class activation. The framework is demonstrated here with convolutional neural networks and transformer models. Using a set of brain data recorded with EEG while participants viewed a stimulus in VR designed to elicit cybersickness, we show which spatio-temporal EEG features (from electrodes and time steps) were most important for discomfort classification. Across 12 runs of our framework with three different neural networks over multiple random seeds, the models consistently pointed to the same scalp locations as having patterns of brain data that were the most helpful in determining whether or not a sample of EEG data belonged to someone who was experiencing cybersickness. These results help clarify a hidden pattern in other related research and can be used as tagged features for better real-time cybersickness classification with EEG in the future. We provide our code at [anonymized] to enable feature interpretation across different neural network architectures.

Aref Amiri, Steven M. LaValle

Feedback motion planning over cell decompositions provides a robust method for generating collision-free robot motion with formal guarantees. However, existing algorithms often produce paths with unnecessary bending, leading to slower motion and higher control effort. This paper presents a computationally efficient method to mitigate this issue for a given simplicial decomposition. A heuristic is introduced that systematically aligns and assigns local vector fields to produce more direct trajectories, complemented by a novel geometric algorithm that constructs a maximal star-shaped chain of simplexes around the goal. This creates a large ``funnel'' in which an optimal, direct-to-goal control law can be safely applied. Simulations demonstrate that our method generates measurably more direct paths, reducing total bending by an average of 91.40\% and LQR control effort by an average of 45.47\%. Furthermore, comparative analysis against sampling-based and optimization-based planners confirms the time efficacy and robustness of our approach. While the proposed algorithms work over any finite-dimensional simplicial complex embedded in the collision-free subset of the configuration space, the practical application focuses on low-dimensional ($d\le3$) configuration spaces, where simplicial decomposition is computationally tractable.

Filip V. Georgiev, Kalle G. Timperi, Başak Sakçak et al.

This paper bridges some of the gap between optimal planning and reinforcement learning (RL), both of which share roots in dynamic programming applied to sequential decision making or optimal control. Whereas planning typically favors deterministic models, goal termination, and cost minimization, RL tends to favor stochastic models, infinite-horizon discounting, and reward maximization in addition to learning-related parameters such as the learning rate and greediness factor. A derandomized version of RL is developed, analyzed, and implemented to yield performance comparisons with value iteration and Dijkstra's algorithm using simple planning models. Next, mathematical analysis shows: 1) conditions under which cost minimization and reward maximization are equivalent, 2) conditions for equivalence of single-shot goal termination and infinite-horizon episodic learning, and 3) conditions under which discounting causes goal achievement to fail. The paper then advocates for defining and optimizing truecost, rather than inserting arbitrary parameters to guide operations. Performance studies are then extended to the stochastic case, using planning-oriented criteria and comparing value iteration to RL with learning rates and greediness factors.

Nikunj Arora, Markku Suomalainen, Matti Pouke et al.

We propose augmenting immersive telepresence by adding a virtual body, representing the user's own arm motions, as realized through a head-mounted display and a 360-degree camera. Previous research has shown the effectiveness of having a virtual body in simulated environments; however, research on whether seeing one's own virtual arms increases presence or preference for the user in an immersive telepresence setup is limited. We conducted a study where a host introduced a research lab while participants wore a head-mounted display which allowed them to be telepresent at the host's physical location via a 360-degree camera, either with or without a virtual body. We first conducted a pilot study of 20 participants, followed by a pre-registered 62 participant confirmatory study. Whereas the pilot study showed greater presence and preference when the virtual body was present, the confirmatory study failed to replicate these results, with only behavioral measures suggesting an increase in presence. After analyzing the qualitative data and modeling interactions, we suspect that the quality and style of the virtual arms, and the contrast between animation and video, led to individual differences in reactions to the virtual body which subsequently moderated feelings of presence.

Markku Suomalainen, Basak Sakcak, Adhi Widagdo et al.

We propose unwinding the rotations experienced by the user of an immersive telepresence robot to improve comfort and reduce VR sickness of the user. By immersive telepresence we refer to a situation where a 360\textdegree~camera on top of a mobile robot is streaming video and audio into a head-mounted display worn by a remote user possibly far away. Thus, it enables the user to be present at the robot's location, look around by turning the head and communicate with people near the robot. By unwinding the rotations of the camera frame, the user's viewpoint is not changed when the robot rotates. The user can change her viewpoint only by physically rotating in her local setting; as visual rotation without the corresponding vestibular stimulation is a major source of VR sickness, physical rotation by the user is expected to reduce VR sickness. We implemented unwinding the rotations for a simulated robot traversing a virtual environment and ran a user study (N=34) comparing unwinding rotations to user's viewpoint turning when the robot turns. Our results show that the users found unwound rotations more preferable and comfortable and that it reduced their level of VR sickness. We also present further results about the users' path integration capabilities, viewing directions, and subjective observations of the robot's speed and distances to simulated people and objects.

Markku Suomalainen, Katherine J. Mimnaugh, Israel Becerra et al.

In this paper, we analyze how different path aspects affect a user's experience, mainly VR sickness and overall comfort, while immersed in an autonomously moving telepresence robot through a virtual reality headset. In particular, we focus on how the robot turns and the distance it keeps from objects, with the goal of planning suitable trajectories for an autonomously moving immersive telepresence robot in mind; rotational acceleration is known for causing the majority of VR sickness, and distance to objects modulates the optical flow. We ran a within-subjects user study (n = 36, women = 18) in which the participants watched three panoramic videos recorded in a virtual museum while aboard an autonomously moving telepresence robot taking three different paths varying in aspects such as turns, speeds, or distances to walls and objects. We found a moderate correlation between the users' sickness as measured by the SSQ and comfort on a 6-point Likert scale across all paths. However, we detected no association between sickness and the choice of the most comfortable path, showing that sickness is not the only factor affecting the comfort of the user. The subjective experience of turn speed did not correlate with either the SSQ scores or comfort, even though people often mentioned turning speed as a source of discomfort in the open-ended questions. Through exploring the open-ended answers more carefully, a possible reason is that the length and lack of predictability also play a large role in making people observe turns as uncomfortable. A larger subjective distance from walls and objects increased comfort and decreased sickness both in quantitative and qualitative data. Finally, the SSQ subscales and total weighted scores showed differences by age group and by gender.

Katherine J. Mimnaugh, Markku Suomalainen, Israel Becerra et al.

This paper considers how the motions of a telepresence robot moving autonomously affect a person immersed in the robot through a head-mounted display. In particular, we explore the preference, comfort, and naturalness of elements of piecewise linear paths compared to the same elements on a smooth path. In a user study, thirty-six subjects watched panoramic videos of three different paths through a simulated museum in virtual reality and responded to questionnaires regarding each path. Preference for a particular path was influenced the most by comfort, forward speed, and characteristics of the turns. Preference was also strongly associated with the users' perceived naturalness, which was primarily determined by the ability to see salient objects, the distance to the walls and objects, as well as the turns. Participants favored the paths that had a one meter per second forward speed and rated the path with the least amount of turns as the most comfortable

Katherine J. Mimnaugh, Markku Suomalainen, Israel Becerra et al.

This paper presents some early work and future plans regarding how the autonomous motions of a telepresence robot affect a person embodied in the robot through a head-mounted display. We consider the preferences, comfort, and the perceived naturalness of aspects of piecewise linear paths compared to the same aspects on a smooth path. In a user study, thirty-six subjects (eighteen females) watched panoramic videos of three different paths through a simulated museum in virtual reality and responded to questionnaires regarding each path. We found that comfort had a strong effect on path preference, and that the subjective feeling of naturalness also had a strong effect on path preference, even though people consider different things as natural. We describe a categorization of the responses regarding the naturalness of the robot's motion and provide a recommendation on how this can be applied more broadly. Although immersive robotic telepresence is increasingly being used for remote education, clinical care, and to assist people with disabilities or mobility complications, the full potential of this technology is limited by issues related to user experience. Our work addresses these shortcomings and will enable the future personalization of telepresence experiences for the improvement of overall remote communication and the enhancement of the feeling of presence in a remote location.

Matti Pouke, Katherine J. Mimnaugh, Alexis Chambers et al.

This paper identifies and confirms a perceptual phenomenon: when users interact with simulated objects in a virtual environment where the users' scale deviates greatly from normal, there is a mismatch between the object physics they consider realistic and the object physics that would be correct at that scale. We report the findings of two studies investigating the relationship between perceived realism and a physically accurate approximation of reality in a virtual reality experience in which the user has been scaled by a factor of ten. Study 1 investigated perception of physics when scaled-down by a factor of ten, whereas Study 2 focused on enlargement by a similar amount. Studies were carried out as within-subjects experiments in which a total of 84 subjects performed simple interaction tasks with objects under two different physics simulation conditions. In the true physics condition, the objects, when dropped and thrown, behaved accurately according to the physics that would be correct at that either reduced or enlarged scale in the real world. In the movie physics condition, the objects behaved in a similar manner as they would if no scaling of the user had occurred. We found that a significant majority of the users considered the movie physics condition to be the more realistic one. However, at enlarged scale, many users considered true physics to match their expectations even if they ultimately believed movie physics to be the realistic condition. We argue that our findings have implications for many virtual reality and telepresence applications involving operation with simulated or physical objects in abnormal and especially small scales.

Alexandra Q. Nilles, Ana Pervan, Thomas A. Berrueta et al.

We present a task-centered formal analysis of the relative power of several robot designs, inspired by the unique properties and constraints of micro-scale robotic systems. Our task of interest is object manipulation because it is a fundamental prerequisite for more complex applications such as micro-scale assembly or cell manipulation. Motivated by the difficulty in observing and controlling agents at the micro-scale, we focus on the design of boundary interactions: the robot's motion strategy when it collides with objects or the environment boundary, otherwise known as a bounce rule. We present minimal conditions on the sensing, memory, and actuation requirements of periodic ``bouncing'' robot trajectories that move an object in a desired direction through the incidental forces arising from robot-object collisions. Using an information space framework and a hierarchical controller, we compare several robot designs, emphasizing the information requirements of goal completion under different initial conditions, as well as what is required to recognize irreparable task failure. Finally, we present a physically-motivated model of boundary interactions, and analyze the robustness and dynamical properties of resulting trajectories.

Israel Becerra, Markku Suomalainen, Eliezer Lozano et al.

This paper introduces an emerging motion planning problem by considering a human that is immersed into the viewing perspective of a remote robot. The challenge is to make the experience both effective (such as delivering a sense of presence) and comfortable (such as avoiding adverse sickness symptoms, including nausea). We refer to this challenging new area as human perception-optimized planning and propose a general multiobjective optimization framework that can be instantiated in many envisioned scenarios. We then consider a specific VR telepresence task as a case of human perception-optimized planning, in which we simulate a robot that sends 360 video to a remote user to be viewed through a head-mounted display. In this particular task, we plan trajectories that minimize VR sickness (and thereby maximize comfort). An A* type method is used to create a Pareto-optimal collection of piecewise linear trajectories while taking into account criteria that improve comfort. We conducted a study with human subjects touring a virtual museum, in which paths computed by our algorithm are compared against a reference RRT-based trajectory. Generally, users suffered less from VR sickness and preferred the paths created by the presented algorithm.

Matti Pouke, Katherine J. Mimnaugh, Timo Ojala et al.

This paper identifies a new phenomenon: when users interact with simulated objects in a virtual environment where the user is much smaller than usual, there is a mismatch between the object physics that they expect and the object physics that would be correct at that scale. We report the findings of our study investigating the relationship between perceived realism and a physically accurate approximation of reality in a virtual reality experience in which the user has been scaled down by a factor of ten. We conducted a within-subjects experiment in which 44 subjects performed a simple interaction task with objects under two different physics simulation conditions. In one condition, the objects, when dropped and thrown, behaved accurately according to the physics that would be correct at that reduced scale in the real world, our true physics condition. In the other condition, the movie physics condition, the objects behaved in a similar manner as they would if no scaling of the user had occurred. We found that a significant majority of the users considered the latter condition to be the more realistic one. We argue that our findings have implications for many virtual reality and telepresence applications involving operation with simulated or physical objects in small scales.

Markku Suomalainen, Alexandra Q. Nilles, Steven M. LaValle

This paper applies the principles of Virtual Reality (VR) to robots, rather than living organisms. A simulator, of either physical states or information states, renders outputs to custom displays that fool the robot's sensors. This enables a robot to experience a combination of real and virtual sensor inputs, combining the efficiency of simulation and the benefits of real world sensor inputs. Thus, the robot can be taken through targeted experiences that are more realistic than pure simulation, yet more feasible and controllable than pure real-world experiences. We define two distinctive methods for applying VR to robots, namely black box and white box; based on these methods we identify potential applications, such as testing and verification procedures that are better than simulation, the study of spoofing attacks and anti-spoofing techniques, and sample generation for machine learning. A general mathematical framework is presented, along with a simple experiment, detailed examples, and discussion of the implications.

Jingjin Yu, Steven M. LaValle

We study the problem of optimal multi-robot path planning on graphs MPP over four distinct minimization objectives: the makespan (last arrival time), the maximum (single-robot traveled) distance, the total arrival time, and the total distance. In a related paper, we show that these objectives are distinct and NP-hard to optimize. In this work, we focus on efficiently algorithmic solutions for solving these optimal MPP problems. Toward this goal, we first establish a one-to-one solution mapping between MPP and network-flow. Based on this equivalence and integer linear programming (ILP), we design novel and complete algorithms for optimizing over each of the four objectives. In particular, our exact algorithm for computing optimal makespan solutions is a first such that is capable of solving extremely challenging problems with robot-vertex ratio as high as 100%. Then, we further improve the computational performance of these exact algorithms through the introduction of principled heuristics, at the expense of some optimality loss. The combination of ILP model based algorithms and the heuristics proves to be highly effective, allowing the computation of 1.x-optimal solutions for problems containing hundreds of robots, densely populated in the environment, often in just seconds.

Jingjin Yu, Steven M. LaValle

We study the problem of optimal multi-robot path planning on graphs (MPP) over four distinct minimization objectives: the total arrival time, the makespan (last arrival time), the total distance, and the maximum (single-robot traveled) distance. On the structure side, we show that each pair of these four objectives induces a Pareto front and cannot always be optimized simultaneously. Then, through reductions from 3-SAT, we further establish that computation over each objective is an NP-hard task, providing evidence that solving MPP optimally is generally intractable. Nevertheless, in a related paper, we design complete algorithms and efficient heuristics for optimizing all four objectives, capable of solving MPP optimally or near-optimally for hundreds of robots in challenging setups.

Steven M. LaValle, Seth A. Hutchinson

In this paper we address the uncertainty issues involved in the low-level vision task of image segmentation. Researchers in computer vision have worked extensively on this problem, in which the goal is to partition (or segment) an image into regions that are homogeneous or uniform in some sense. This segmentation is often utilized by some higher level process, such as an object recognition system. We show that by considering uncertainty in a Bayesian formalism, we can use statistical image models to build an approximate representation of a probability distribution over a space of alternative segmentations. We give detailed descriptions of the various levels of uncertainty associated with this problem, discuss the interaction of prior and posterior distributions, and provide the operations for constructing this representation.

Jingjin Yu, Steven M. LaValle

This paper connects multi-agent path planning on graphs (roadmaps) to network flow problems, showing that the former can be reduced to the latter, therefore enabling the application of combinatorial network flow algorithms, as well as general linear program techniques, to multi-agent path planning problems on graphs. Exploiting this connection, we show that when the goals are permutation invariant, the problem always has a feasible solution path set with a longest finish time of no more than $n + V - 1$ steps, in which $n$ is the number of agents and $V$ is the number of vertices of the underlying graph. We then give a complete algorithm that finds such a solution in $O(nVE)$ time, with $E$ being the number of edges of the graph. Taking a further step, we study time and distance optimality of the feasible solutions, show that they have a pairwise Pareto optimal structure, and again provide efficient algorithms for optimizing two of these practical objectives.

Jingjin Yu, Steven M. LaValle

In this paper, we study the problem of optimal multi-robot path planning (MPP) on graphs. We propose two multiflow based integer linear programming (ILP) models that computes minimum last arrival time and minimum total distance solutions for our MPP formulation, respectively. The resulting algorithms from these ILP models are complete and guaranteed to yield true optimal solutions. In addition, our flexible framework can easily accommodate other variants of the MPP problem. Focusing on the time optimal algorithm, we evaluate its performance, both as a stand alone algorithm and as a generic heuristic for quickly solving large problem instances. Computational results confirm the effectiveness of our method.

Jingjin Yu, Steven M. LaValle

For the task of moving a set of indistinguishable agents on a connected graph with unit edge distance to an arbitrary set of goal vertices, free of collisions, we propose a fast distance optimal control algorithm that guides the agents into the desired formation. Moreover, we show that the algorithm also provides a tight convergence time guarantee (time optimality and distance optimality cannot be simultaneously satisfied). Our generic graph formulation allows the algorithm to be applied to scenarios such as grids with holes (modeling obstacles) in arbitrary dimensions. Simulations, available online, confirm our theoretical developments.