This article discusses the integration challenges and strategies for designing mobile robots, by focusing on the task-driven, optimal selection of hardware and software to balance safety, efficiency, and minimal usage of resources such as costs, energy, computational requirements, and weight. We emphasize the interplay between perception and motion planning in decision-making by introducing the concept of occupancy queries to quantify the perception requirements for sampling-based motion planners. Sensor and algorithm performance are evaluated using false negative rate and false positive rate across various factors such as geometric relationships, object properties, sensor resolution, and environmental conditions. By integrating perception requirements with perception performance, an integer linear programming approach is proposed for efficient sensor and algorithm selection and placement. This forms the basis for a co-design optimization that includes the robot body, motion planner, perception pipeline, and computing unit. We refer to this framework for solving the co-design problem of mobile robots as CODEI, short for co-design of embodied intelligence. A case study on developing an autonomous vehicle for urban scenarios provides actionable information for designers, and shows that complex tasks escalate resource demands, with task performance affecting choices of the autonomy stack. The study demonstrates that resource prioritization influences sensor choice: cameras are preferred for cost-effective and lightweight designs, while lidar sensors are chosen for better energy and computational efficiency.

Autonomous Mobility-on-Demand (AMoD) systems, powered by advances in robotics, control, and Machine Learning (ML), offer a promising paradigm for future urban transportation. AMoD offers fast and personalized travel services by leveraging centralized control of autonomous vehicle fleets to optimize operations and enhance service performance. However, the rapid growth of this field has outpaced the development of standardized practices for evaluating and reporting results, leading to significant challenges in reproducibility. As AMoD control algorithms become increasingly complex and data-driven, a lack of transparency in modeling assumptions, experimental setups, and algorithmic implementation hinders scientific progress and undermines confidence in the results. This paper presents a systematic study of reproducibility in AMoD research. We identify key components across the research pipeline, spanning system modeling, control problems, simulation design, algorithm specification, and evaluation, and analyze common sources of irreproducibility. We survey prevalent practices in the literature, highlight gaps, and propose a structured framework to assess and improve reproducibility. While focused on AMoD, the principles and practices we advocate generalize to a broader class of cyber-physical systems that rely on networked autonomy and data-driven control. This work aims to lay the foundation for a more transparent and reproducible research culture in the design and deployment of intelligent mobility systems.

This paper presents a formal specification framework for planning and control of autonomous robots, focusing on the challenge of managing complex trade-offs among multiple, potentially conflicting objectives. These include hierarchical relationships and non-comparable objectives, some of which may be too complex to be captured by standard additive cost functions. We leverage therulebookformalism to represent such objectives and their relationships and formulate two control synthesis problems: single-strategy synthesis, which seeks one optimal strategy, and complete synthesis, which computes the full set of optimal strategies with respect to a rulebook, analogous to the Pareto front in multi-objective planning. We show that our formulation generalizes existing temporal logic-based and optimization-based planning and control, providing a unifying framework across robotics, formal methods, control theory, and operations research. For single-strategy, we identify tractable subclasses and present a polynomial-time algorithm that accommodates richer combinations of objectives than prior work. For complete synthesis, we introduce an algorithm to compute all optimal solutions and analyze its computational complexity. In both cases, we present case studies that include complex multi-objective planning problems and demonstrate the practical effectiveness of our approach compared to existing methods.

This article discusses the integration challenges and strategies for designing mobile robots, by focusing on the task-driven, optimal selection of hardware and software to balance safety, efficiency, and minimal usage of resources such as costs, energy, computational requirements, and weight. We emphasize the interplay between perception and motion planning in decision-making by introducing the concept of occupancy queries to quantify the perception requirements for sampling-based motion planners. Sensor and algorithm performance are evaluated using false negative rate and false positive rate across various factors such as geometric relationships, object properties, sensor resolution, and environmental conditions. By integrating perception requirements with perception performance, an integer linear programming approach is proposed for efficient sensor and algorithm selection and placement. This forms the basis for a co-design optimization that includes the robot body, motion planner, perception pipeline, and computing unit. We refer to this framework for solving the co-design problem of mobile robots as CODEI, short for co-design of embodied intelligence. A case study on developing an autonomous vehicle for urban scenarios provides actionable information for designers, and shows that complex tasks escalate resource demands, with task performance affecting choices of the autonomy stack. The study demonstrates that resource prioritization influences sensor choice: cameras are preferred for cost-effective and lightweight designs, while lidar sensors are chosen for better energy and computational efficiency.

No abstract available.

In recent years, driving context perception has emerged as one of the key aspects to design driving assistance algorithms and user interfaces that are effective in adapting to different traffic situations or environments. To this aim, we introduce the Anonymous Driving Scene Perception (ADSP) Model, a novel deep neural network designed to classify anony-mous Controller Area Network (CAN)-bus data into multiple driving context domains. ADSP extends the idea of driving scene classification to time series signals, as previous works relied heavily on visual features. Our model achieved a multi -domain classification accuracy of 84.9% on our custom-built naturalistic data set, as a combination of 92.7% on road type classification and 90.1 % on binary traffic detection, performing 2.0% and 1.6% better than the state-of-the-art model for multivariate time series classification. Our work demonstrates the feasibility of driving scene classification from anonymous CAN-bus data, without collecting sensitive data from users (images or GPS).

Dynamic games feature a state-space complexity that scales superlinearly with the number of players. This makes this class of games often intractable even for a handful of players. We introduce the factorization process of dynamic games as a transformation leveraging the independence of players at equilibrium to build a leaner game graph. When applicable, it yields fewer nodes, fewer players per game node, hence much faster solutions. While for the general case checking for independence of players requires to solve the game itself, we observe that for dynamic games in the robotic domain there exist exact heuristics based on the spatio-temporal occupancy of the individual players. We validate our findings in realistic autonomous driving scenarios showing that already for a 4-player intersection we have a reduction of game nodes and solving time close to 99%.

In recent years, mobility on demand has experienced a major revival due to various ride-hailing companies entering the market. Competing in this field requires an efficient operation. Therefore, the applied policy, which cares for vehicle-to-customer assignment and vehicle repositioning, has to achieve good customer service and minimize cost while trying to keep the impact on the environment as low as possible. A promising approach is to coordinate the control of the entire fleet, which is foreseen to become even easier with the possibility of autonomous vehicles in mind. Anticipating future demand requires a good understanding of the spatiotemporal distributions of request origins and destinations, and the resulting imbalance between vehicle demand and availability. This results from a multitude of topological, demographic, and social effects, which are almost impossible to sufficiently capture in a handcrafted model of reasonable complexity. This can be circumvented by leveraging machine learning approaches. In this paper, an image-like representation of the city and its fleet's state is introduced. It is comprehensive and intuitive to use as input to convolutional neural networks, which in the past have already been proven to capture spatial relationships very well. This allows operating on realistic, full-sized traffic networks without greatly increasing the number of parameters the neural network has to learn and, hence, keeps the training effort low. Additionally, this state is combined with a similarly constructed repositioning action, reflecting a 2D distribution of a well-performing operational policy. This approach allows replacement of complex, handcrafted mathematical models by a single, compact, auto-encoder-like neural network.

We consider the problem of co-designing embodied intelligence as a whole in a structured way, from hardware components such as propulsion systems and sensors to software modules such as control and perception pipelines. We propose a principled approach to formulate and solve complex embodied intelligence co-design problems, leveraging a monotone co-design theory. The methods we propose are intuitive and integrate heterogeneous engineering disciplines, allowing analytical and simulation-based modeling techniques and enabling interdisciplinarity. We illustrate through a case study how, given a set of desired behaviors, our framework is able to compute Pareto efficient solutions for the entire hardware and software stack of a self-driving vehicle.

Plastic neural networks have the ability to adapt to new tasks. However, in a continual learning setting, the configuration of parameters learned in previous tasks can severely reduce the adaptability to future tasks. In particular, we show that, when using weight decay, weights in successive layers of a deep network may become "mutually frozen". This has a double effect: on the one hand, it makes the network updates more invariant to nuisance factors, providing a useful bias for future tasks. On the other hand, it can prevent the network from learning new tasks that require significantly different features. In this context, we find that the local input sensitivity of a deep model is correlated with its ability to adapt, thus leading to an intriguing trade-off between adaptability and invariance when training a deep model more than once. We then show that a simple intervention that "resets" the mutually frozen connections can improve transfer learning on a variety of visual classification tasks. The efficacy of "resetting" itself depends on the size of the target dataset and the difference of the pre-training and target domains, allowing us to achieve state-of-the-art results on some datasets.

In unit-capacity mobility-on-demand systems, the vehicles transport only one travel party at a time, whereas in ride-sharing mobility-on-demand systems, a vehicle may transport different travel parties at the same time, e.g., if paths are partially overlapping. One potential benefit of ride sharing is increased system efficiency. However, it is not clear what the trade-offs are between the efficiency gains and the reduction in quality of service. To quantify those trade-offs, an open-source simulation environment is introduced, which is capable of evaluating a large class of operational policies for ride-sharing mobility-on-demand systems. The impact of ride sharing on efficiency and service level is assessed for several benchmark operational policies from the literature and for different transportation scenarios: first a dense urban scenario, then a line-shaped, rural one. Based on the results of these case studies, we find that the efficiency gains in ride sharing are relatively small and potentially hard to justify against quality of service concerns such as reduced convenience, loss of privacy, and higher total travel and drive times. Furthermore, in the assessed scenarios, the relatively low occupancy of the vehicles suggests that smaller vehicles with 4-6 seats, able to handle occasional ride sharing, may be preferable to larger and more expensive vehicles such as minibuses.

RRT* is one of the most widely used sampling-based algorithms for asymptotically-optimal motion planning. RRT* laid the foundations for optimality in motion planning as a whole, and inspired the development of numerous new algorithms in the field, many of which build upon RRT* itself. In this paper, we first identify a logical gap in the optimality proof of RRT*, which was developed by Karaman and Frazzoli (2011). Then, we present an alternative and mathematically-rigorous proof for asymptotic optimality. Our proof suggests that the connection radius used by RRT* should be increased from γ (log n/n)1/dto γ' (log n/n)1/(d+1)in order to account n n for the additional dimension of time that dictates the samples' ordering. Here γ, γ' are constants, and n, d are the number of samples and the dimension of the problem, respectively.

As robotics matures and increases in complexity, it is more necessary than ever that robot autonomy research be reproducible. Compared to other sciences, there are specific challenges to benchmarking autonomy, such as the complexity of the software stacks, the variability of the hardware and the reliance on data-driven techniques, amongst others. In this paper, we describe a new concept for reproducible robotics research that integrates development and benchmarking, so that reproducibility is obtained "by design" from the beginning of the research/development processes. We first provide the overall conceptual objectives to achieve this goal and then a concrete instance that we have built: the DUCKIENet. One of the central components of this setup is the Duckietown Autolab, a remotely accessible standardized setup that is itself also relatively low-cost and reproducible. When evaluating agents, careful definition of interfaces allows users to choose among local versus remote evaluation using simulation, logs, or remote automated hardware setups. We validate the system by analyzing the repeatability of experiments conducted using the infrastructure and show that there is low variance across different robot hardware and across different remote labs.†

The behavior of self-driving cars must be compatible with an enormous set of conflicting and ambiguous objectives, from law, from ethics, from the local culture, and so on. This paper describes a new way to conveniently define the desired behavior for autonomous agents, which we use on the self-driving cars developed at nuTonomy, an Aptiv company. We define a “rulebook” as a pre-ordered set of “rules”, each akin to a violation metric on the possible outcomes (“realizations”). The rules are partially ordered by priority. The semantics of a rulebook imposes a pre-order on the set of realizations. We study the compositional properties of the rulebooks, and we derive which operations we can allow on the rulebooks to preserve previously-introduced constraints. While we demonstrate the application of these techniques in the self-driving domain, the methods are domain-independent.

One of the challenges of developing autonomous vehicles is planning in an inhabited environment under sensing uncertainty as well as limited perception and computational resources. Besides reasoning about the behaviour of traffic participants that are within the vehicles' field of view, safe autonomous driving also requires the vehicle to reason about possible traffic participants that might exist beyond its sensing horizon, and to adapt its driving behaviour accordingly. This paper describes an inference and motion planning pipeline that is able to guarantee passive safety (collisions are possible, but the autonomous vehicle will be at rest) with respect to hypothetical hidden agents that have not been observed yet. We also incorporate the vehicle's reaction time due to sensing and computational delays into the planning process; for example, we show how having a fast reaction time due to the availability of more computational resources leads to more aggressive trajectories, while a car with a larger reaction time will choose more relaxed trajectories that require less attention.

This paper presents a model predictive control (MPC) approach to optimize routes for Ride-sharing Autonomous Mobility-on-Demand (RAMoD) systems, whereby self-driving vehicles provide coordinated on-demand mobility, possibly allowing multiple customers to share a ride. Specifically, we first devise a time-expanded network flow model for RAMoD. Second, leveraging this model, we design a real-time MPC algorithm to optimize the routes of both empty and customer-carrying vehicles, with the goal of optimizing social welfare, namely, a weighted combination of customers' travel time and vehicles' mileage. Finally, we present a real-world case study for the city of San Francisco, CA, by using the micro-scopic traffic simulator MATSim. The simulation results show that a RAMoD system can significantly improve social welfare with respect to a single-occupancy Autonomous Mobility-on-Demand (AMoD) system, and that the predictive structure of the proposed MPC controller allows it to outperform existing reactive ride-sharing coordination algorithms for RAMoD.

Typically, to enlarge the operating domain of an object detector, more labeled training data is required. We describe a method called wormhole learning, which allows to extend the operating domain without additional data, but only with temporary access to an auxiliary sensor with certain invariance properties. We describe the instantiation of this principle with a regular visible-light RGB camera as the main sensor, and an infrared sensor as the temporary sensor. We start with a pre-trained RGB detector; then we train the infrared detector based on the RGB-inferred labels; finally we re-train the RGB detector based on the infrared-inferred labels. After these two transfer-learning steps, the RGB detector has enlarged its operating domain by inheriting part of the invariance to illumination of the infrared sensor; in particular, the RGB detector is now able to see much better at night. We analyze the wormhole learning phenomenon by bounding the possible gain in accuracy using mutual information properties of the two sensors and considered operating domain.

We propose a novel optimal receding-horizon navigation approach for a robot in an unknown search environment, towards a known goal position. The search environment includes several obstacles that are distributed at unknown positions. The proposed approach considers multiple objectives, including reference path tracking, reduction of the energy consumption, restraining the robot's mission time, and asymptotic stability towards the goal position. The navigation policy is determined in the detection zone of the robot's detection sensor at particular update time steps for short time. This policy will be updated at the next update time steps. Moreover, we introduce a novel heuristic algorithm for determining the robot's tracking path trajectory that is simply implementable and fast in computations.

In this article, we consider the problem of attack-resilient state estimation, that is, to reliably estimate the true system states despite two classes of attacks: (i) attacks on the switching mechanisms and (ii) false data injection attacks on actuator and sensor signals, in the presence of stochastic process and measurement noise signals. We model the systems under attack as hidden mode stochastic switched linear systems with unknown inputs and propose the use of a multiple-model inference algorithm to tackle these security issues. Moreover, we characterize fundamental limitations to resilient estimation (e.g., upper bound on the number of tolerable signal attacks) and discuss the topics of attack detection, identification, and mitigation under this framework. Simulation examples of switching and false data injection attacks on a benchmark system and an IEEE 68-bus test system show the efficacy of our approach to recover resilient (i.e., asymptotically unbiased) state estimates as well as to identify and mitigate the attacks.

Constraint on the actuation and power resources is often the critical limiting factor for a robot to perform desired tasks. Increasing torque and energy capacity may be a solution, but is seldom viable for robots already built. An attractive alternative is to carefully generate motion trajectories that maximally leverages upon the limited torque and energy resources. In this endeavor, singularity, which is deemed undesirable due to lose of manipulability, could be utilized to an advantage. This paper presents analysis of force and momentum generated through contact in relation to the singularity. The analysis shows that a motion at or near singularity not only maximally leverages the torque limits to generate forces in quasi-static motions, but is also optimally energy efficient for dynamical motion when it comes to momentum generation. Based on a simplified model, we discuss mechanical advantage aspects of a robotic leg and describe range of feasible forces that can be generated together with directions in which singular position becomes minimum torque configuration. Then we define stroke motion and establish upper bounds on the momentum generated through contact. Collinear stroke, where motion is along a straight line, is examined with respect to singularity.

Duckietown is an open, inexpensive and flexible platform for autonomy education and research. The platform comprises small autonomous vehicles (“Duckiebots”) built from off-the-shelf components, and cities (“Duckietowns”) complete with roads, signage, traffic lights, obstacles, and citizens (duckies) in need of transportation. The Duckietown platform offers a wide range of functionalities at a low cost. Duckiebots sense the world with only one monocular camera and perform all processing onboard with a Raspberry Pi 2, yet are able to: follow lanes while avoiding obstacles, pedestrians (duckies) and other Duckiebots, localize within a global map, navigate a city, and coordinate with other Duckiebots to avoid collisions. Duckietown is a useful tool since educators and researchers can save money and time by not having to develop all of the necessary supporting infrastructure and capabilities. All materials are available as open source, and the hope is that others in the community will adopt the platform for education and research.

A landmark based heuristic is investigated for reducing query phase run-time of the probabilistic roadmap (PRM) motion planning method. The heuristic is generated by storing minimum spanning trees from a small number of vertices within the PRM graph and using these trees to approximate the cost of a shortest path between any two vertices of the graph. The intermediate step of preprocessing the graph increases the time and memory requirements of the classical motion planning technique in exchange for speeding up individual queries making the method advantageous in multi-query applications. This paper investigates these trade-offs on PRM graphs constructed in randomized environments as well as a practical manipulator simulation. We conclude that the method is preferable to Dijkstra's algorithm or the A* algorithm with conventional heuristics in multi-query applications.

The partially observable Markov decision process (POMDP) provides a principled general model for planning under uncertainty. However, solving a general POMDP is computationally intractable in the worst case. This paper introduces POMDP-lite, a subclass of POMDPs in which the hidden state variables are constant or only change deterministically. We show that a POMDP-lite is equivalent to a set of fully observable Markov decision processes indexed by a hidden parameter and is useful for modeling a variety of interesting robotic tasks. We develop a simple model-based Bayesian reinforcement learning algorithm to solve POMDP-lite models. The algorithm performs well on large-scale POMDP-lite models with up to 1020 states and outperforms the state-of-the-art general-purpose POMDP algorithms. We further show that the algorithm is near-Bayesian-optimal under suitable conditions.

One of the standing challenges in multi-robot systems is the ability to reliably coordinate motions of multiple robots in environments where the robots are subject to disturbances. We consider disturbances that force the robot to temporarily stop and delay its advancement along its planned trajectory which can be used to model, e.g., passing-by humans for whom the robots have to yield. Although reactive collision-avoidance methods are often used in this context, they may lead to deadlocks between robots. We design a multi-robot control strategy for executing coordinated trajectories computed by a multi-robot trajectory planner and give a proof that the strategy is safe and deadlock-free even when robots are subject to delaying disturbances. Our simulations show that the proposed strategy scales significantly better with the intensity of disturbances than the naive liveness-preserving approach. The empirical results further confirm that the proposed approach is more reliable and also more efficient than state-of-the-art reactive techniques.

In this work, we address the problem of robust data association for feature cloud matching. For matching two feature clouds observed at two different poses, we discover that the covariance matrix of the measurement prediction error can be written as the sum of a low rank matrix and a block diagonal matrix, if we assume that the features are observed independently at each pose. This special structure of the covariance matrix allows us to compute its inverse analytically and efficiently. Together with a good bookkeeping strategy, the complexity of the Joint Compatibility (JC) test is reduced to O(1). Contrary to the approximated JC test, ours is both exact and fast. Based on the efficient JC test algorithm and a branch and bound search procedure, we devise an algorithm, called Fast Joint Compatibility Branch and Bound (FastJCBB), to quickly obtain robust data association. The FastJCBB algorithm is essentially modified from the conventional Joint Compatibility Branch and Bound (JCBB) algorithm and both of these algorithms are able to produce exactly the same data association results. However, with the substantial improvement in the efficiency of JC tests, our FastJCBB algorithm is much faster than the conventional JCBB, especially when matching two large feature clouds. It is reported that our FastJCBB algorithm is more than 740 times faster than the conventional JCBB in carrying out one million JC tests when matching two clouds with about 100 features each. Since both FastJCBB and JCBB share the same branch and bound procedure in exploring the interpretation tree, the search complexity remains exponential. Our main contribution is the significant improvement in the efficiency of exploring each node of the interpretation tree.

There is considerable freedom in choosing the sensors to be equipped on a robot. Currently many sensing technologies are available (radar, lidar, vision sensors, time-of-flight cameras, etc.). For each class, there are additional choices regarding the exact sensor parameters (spatial resolution, frame rate, etc.). Which sensor is best? In general, this question needs to be qualified. It depends on the task. In an estimation task, the answer depends on the prior for the signal. In a control task, the answer depends exactly on which are the sufficient statistics for computing the control signal. This paper shows that an ulterior qualification that needs to be made: the answer depends on the power available for sensing, even when the task is fixed. We define the “power-performance” curve as the performance attainable on a task for a given level of sensing power. We show that this approach is well suited to comparing a traditional CMOS sensor with the recently available “neuromorphic” sensors. We discuss estimation tasks with different priors for the signal. We find priors for which one sensor dominates the other and vice-versa, priors for which they are equivalent, and priors for which the answer depends on the power available. This shows that comparing sensors is a quite delicate problem. It also suggests that the optimal architecture might have more that one sensor, and would switch sensors on and off according to the performance level required instantaneously.

The RRT* algorithm has efficiently extended Rapidly-exploring Random Trees (RRTs) to endow it with asymptotic optimality. We propose Goal-Rooted Feedback Motion Trees (GR-FMTs) that honor state/input constraints and generate collision-free feedback policies. Given analytic solutions for optimal local steering, GR-FMTs obtain and realize safe, dynamically feasible, and asymptotically optimal trajectories toward goals. Second, for controllable linear systems with linear state/input constraints, we propose a fast method for local steering, based on polynomial basis functions and segmentation. GR-FMTs with the method obtain and realize trajectories that are collision-free, dynamically feasible under constraints, and asymptotically optimal within a set we define. The formulation includes linear or quadratic programming of small sizes, where constraints are identified by root-finding in low or medium order of polynomials and added progressively.

We detail the design of autonomous golf cars which were used in public trials in Singapore's Chinese and Japanese Gardens, for the purpose of raising public awareness and gaining user acceptance of autonomous vehicles. The golf cars were designed to be robust, reliable, and safe, while operating under prolonged durations. Considerations that went in to the overall system design included the fact that any member of the public had to not only be able to easily use the system, but to also not have the option to use the system in an unintended manner. This paper details the hardware and software components of the golf cars with these considerations, and also how the booking system and mission planner facilitated users to book for a golf car from any of ten stations within the gardens. We show that the vehicles performed robustly throughout the prolonged operations with a small localization variance, and that users were very receptive from the user survey results.

In a mixed environment of autonomous driverless vehicles and human driven vehicles operating on the same road, identifying intentions of human drivers and interacting with them in a compliant and responsible manner becomes a challenging problem for the driverless vehicles. In this paper, the problem of vehicle interaction at an intersection merging scenario is formulated as an Intention-Aware motion planning problem using the tools from Mixed Observability Markov Decision Process (MOMDP). We utilize the tools from recent intention aware planning framework to demonstrate a merging behavior in the presence of human drivers by trying to infer and act according to the intentions of the human drivers. A driver behavior model for T-junction intersections is developed in order to calculate the probabilistic state transition functions of the MOMDP model. With proposed solution, it is demonstrated that using intention aware planning improves performance in comparison to present time to merge approach by lowering accident probability and intersection navigation duration. The proposed method is tested on a real autonomous vehicle (AV) in the presence of human driven vehicles to validate our approach.

In this paper, we present a multivehicle cooperative driving system architecture using cooperative perception along with experimental validation. For this goal, we first propose a multimodal cooperative perception system that provides see-through, lifted-seat, satellite and all-around views to drivers. Using the extended range information from the system, we then realize cooperative driving by a see-through forward collision warning, overtaking/lane-changing assistance, and automated hidden obstacle avoidance. We demonstrate the capabilities and features of our system through real-world experiments using four vehicles on the road.

In this paper, we investigate the behavior of agents in mean field games where each agent evolves according to a dynamic equation containing the input average and seeks to minimize its long time average (LTA) cost encompassing a population state average (PSA), which is also known as the mean field term. Due to the informational burden resulting from the PSA coupling to the states of all agents, our idea is to find a deterministic function φ to approximate it. It is shown that φ is an approximation of the PSA as the population size N goes to infinity. The resulting decentralized mean field control laws lead the system to achieve mean-consensus asymptotically as time goes to infinity. Furthermore, the optimal controls generate an almost sure asymptotic Nash equilibrium, which implies that the LTA cost of each agent can reach its minimal value as the number of agents increases to infinity. Finally, we consider the socially optimal case where the basic objective is to minimize the social cost as the sum of the individual LTA cost containing the PSA. In this case, it is shown that the decentralized mean field social control strategies are the same as the mean field Nash controls for infinite population systems.

We present an any-com algorithm that enables a decentralized team of robots to share the work of collision checking while each robot independently calculates its own motion plan. In our method “safety-certificates” (i.e., bounds on the collision-free subspace around each collision-checked point [1]), are shared among the team so that all robots can benefit from their encoded knowledge. Future points drawn from within a certificate are guaranteed to be safe; therefore, sharing certificates among team members reduces collision checking for all robots. Experiments demonstrate that our algorithm scales well vs. both team size and vs. communication quality.

This paper proposes a semantic mapping method based on pedestrian activity in the urban road environment. Pedestrian activity patterns are learned from pedestrian tracks collected by a mobile platform. With the learned knowledge of pedestrian activity, semantic mapping is performed using Bayesian classification techniques. The proposed method is tested in real experiments, and shows promising results in recognizing four activity-related semantic properties of the urban road environment: pedestrian path, entrance/exit, pedestrian crossing and sidewalk.

This paper investigates motion-planning using formal language specifications for dynamical systems with differential constraints. In particular, we focus on process algebra as a language to specify complex task specifications motivated by autonomous electric vehicles operating in a mobility-on-demand scenario. We use ideas from sampling-based motion-planning algorithms to incrementally construct a finite abstraction of the dynamical system as a Kripke structure. Given a task specification expressed as a process graph, we use model checking techniques to construct a weighted product graph of the specification with the Kripke structure. We then devise an algorithm that provably converges to the optimal trajectory of the dynamical system that satisfies the task specification as the number of the states in the Kripke structure goes to infinity. The algorithm is demonstrated in simulation experiments, viz., charging the electric car at a busy charging station and scheduling pick-ups and drop-offs of passengers.

We consider a class of multi-robot motion planning problems where each robot is associated with multiple objectives and decoupled task specifications. The problems are formulated as an open-loop non-cooperative differential game. A distributed anytime algorithm is proposed to compute a Nash equilibrium of the game. The following properties are proven: (i) the algorithm asymptotically converges to the set of Nash equilibrium; (ii) for scalar cost functionals, the price of stability equals one; (iii) for the worst case, the computational complexity and communication cost are linear in the robot number.

We consider the problem of automatic control strategy synthesis, for discrete models of robotic systems, to fulfill a task that requires reaching a goal state while obeying a given set of safety rules. In this paper, we focus on the case when the said task is not feasible without temporarily violating some of the rules. We propose an algorithm that {synthesizes} a motion which violates only lowest priority rules for the shortest amount of time. Although the proposed algorithm can be applied in a variety of control problems, throughout the paper, we motivate this problem with an autonomous car navigating in an urban environment while abiding by the rules of the road, such as "always stay in the right lane" and "do not enter the sidewalk." We evaluate the algorithm on a case study with several illustrative scenarios.

This paper presents a precise localization algorithm for vehicles in 3D urban environment with only one 2D LIDAR and odometry information. A novel idea of synthetic 2D LIDAR is proposed to solve the localization problem on a virtual 2D plane. A Monte Carlo Localization scheme is adopted for vehicle position estimation, based on synthetic LIDAR measurements and odometry information. The accuracy and robustness of the proposed algorithm are demonstrated by performing real time localization in a 1.5 km driving test around the NUS campus area.

Sampling-based motion planning algorithms, such as the Probabilistic RoadMap (PRM) and the Rapidly-exploring Random Tree (RRT), have received a large and growing amount of attention during the past decade. Most recently, sampling-based algorithms, such as the PRM* and RRT*, that guarantee asymptotic optimality, i.e., almost-sure convergence towards optimal solutions, have been proposed. Despite the experimental success of asymptotically-optimal sampling-based algorithms, their extensions to handle complex non-holonomic dynamical systems remains largely an open problem. In this paper, with the help of results from differential geometry, we extend the RRT* algorithm to handle a large class of non-holonomic dynamical systems. We demonstrate the performance of the algorithm in computational experiments involving the Dubins' car dynamics.

We consider automatic synthesis of control policies for non-independent, heterogeneous multi-agent systems with the objective of maximizing the probability of satisfying a given specification. The specification is expressed as a formula in linear temporal logic. The agents are modeled by Markov decision processes with a common set of actions. These actions, however, may or may not affect the behaviors of all the agents. To alleviate the well-known state explosion problem, an incremental approach is proposed where only a small subset of agents is incorporated in the synthesis procedure initially and more agents are successively added until the limitations on computational resources are reached. The proposed algorithm runs in an anytime fashion, where the probability of satisfying the specification increases as the algorithm progresses.

In sampling-based motion planning algorithms the initial step at every iteration is to generate a new sample from the obstacle-free portion of the configuration space. This is usually accomplished via rejection sampling, i.e., repeatedly drawing points from the entire space until an obstacle-free point is found. This strategy is rarely questioned because the extra work associated with sampling (and then rejecting) useless points contributes at most a constant factor to the planning algorithm's asymptotic runtime complexity. However, this constant factor can be quite large in practice. We propose an alternative approach that enables sampling from a distribution that provably converges to a uniform distribution over only the obstacle-free space. Our method works by storing empirically observed estimates of obstacle-free space in a point-proximity data structure, and then using this information to generate future samples. Both theoretical and experimental results validate our approach.

In this paper, we report a fully automated detailed mapping of a challenging urban environment using single LIDAR. To improve scan matching, extended correlative scan matcher is proposed. Also, a Monte Carlo loop closure detection is implemented to perform place recognition efficiently. Automatic recovery of the pose graph map in the presence of false place recognition is realized through a heuristic based loop closure rejection. This mapping framework is evaluated through experiments on the real world dataset obtained from NUS campus environment.

We consider an approach-evasion differential game where the inputs of one of the players are upper bounded by a random variable. The game enjoys the order preserving property where a larger relaxation of the random variable induces a smaller value function. Two numerical computation algorithms are proposed to asymptotically recover the expected value function. The performance of the proposed algorithms is compared via a stochastically parametric homicidal chauffeur game. The algorithms are also applied to the scenario of merging lanes in urban transportation.

We propose and study the navigation with foraging problem, where an agent with a limited sensor range must simultaneously: (1) navigate to a global goal and (2) forage en route as opportunities to forage are detected. Each foraging act causes a deviation from the shortest path to the long-term goal, with consequences for path length, mission duration, and fuel usage. We analytically calculate and/or bound the expected distance the robot actually travels, given the initial distance to the the global goal. In particular, for either of two non-trivial greedy strategies: (A) forage the point that minimizes goal-heading deviation. (B) forage the closest point ahead of the robot. Our results generalize to problems in higher dimensions.

This paper presents a method of road detection and mapping using accumulated 3D data from 2D scans. The idea of 3D rolling window is introduced, and its probabilistic characteristics are studied. A cascaded road detection process is developed with region-growing and classification methods. A probabilistic framework is utilized for road mapping purposes with the detection results. The performance of detection and mapping algorithm is evaluated through experiments.

In this paper, we consider a class of continuous-time, continuous-space stochastic optimal control problems. Building upon recent advances in Markov chain approximation methods and sampling-based algorithms for deterministic path planning, we propose a novel algorithm called the incremental Markov Decision Process (iMDP) to compute incrementally control policies that approximate arbitrarily well an optimal policy in terms of the expected cost. The main idea behind the algorithm is to generate a sequence of finite discretizations of the original problem through random sampling of the state space. At each iteration, the discretized problem is a Markov Decision Process that serves as an incrementally refined model of the original problem. We show that with probability one, (i) the sequence of the optimal value functions for each of the discretized problems converges uniformly to the optimal value function of the original stochastic optimal control problem, and (ii) the original optimal value function can be computed efficiently in an incremental manner using asynchronous value iterations. Thus, the proposed algorithm provides an anytime approach to the computation of optimal control policies of the continuous problem. The effectiveness of the proposed approach is demonstrated on motion planning and control problems in cluttered environments in the presence of process noise.

Inspired by birds flying through cluttered environments such as dense forests, this paper studies the theoretical foundations of high-speed motion through a randomly-generated obstacle field. Assuming that the locations and the sizes of the trees are determined by an ergodic point process, and under mild technical conditions on the dynamics of the bird, it is shown that the existence of an infinite collision-free trajectory through the forest exhibits a phase transition. In other words, if the bird flies faster than a certain critical speed, there is no infinite collision-free trajectory, with probability one, i.e., the bird will eventually collide with some tree, almost surely, regardless of the planning algorithm governing its motion. On the other hand, if the bird flies slower than this critical speed, then there exists at least one infinite collision-free trajectory, almost surely. Lower and upper bounds on the critical speed are derived for the special case of a Poisson forest considering a simple model for the bird's dynamics. Moreover, results from an extensive Monte-Carlo simulation study are presented. This paper also establishes novel connections between robot motion planning and statistical physics through ergodic theory and the theory of percolation, which may be of independent interest.

One of the most prominent features on an urban road is the curb, which defines the boundary of a road surface. An intersection is a junction of two or more roads, appearing where no curb exists. The combination of curb and intersection features and their idiosyncrasies carry significant information about the urban road network that can be exploited to improve a vehicle's localization. This paper introduces a Monte Carlo Localization (MCL) method using the curb-intersection features on urban roads. We propose a novel idea of “Virtual LIDAR” to get the measurement models for these features. Under the MCL framework, above road observation is fused with odometry information, which is able to yield precise localization. We implement the system using a single tilted 2D LIDAR on our autonomous test bed and show robust performance in the presence of occlusion from other vehicles and pedestrians.

We present an autonomous vehicle providing mobility-on-demand service in a crowded urban environment. The focus in developing the vehicle has been to attain autonomous driving with minimal sensing and low cost, off-the-shelf sensors to ensure the system's economic viability. The autonomous vehicle has successfully completed over 50 km handling numerous mobility requests during the course of multiple demonstrations. The video provides an overview of our approach, with special comments on our localization and perception modules showcasing one such request being serviced.

We consider the synthesis of control policies from temporal logic specifications for robots that interact with multiple dynamic environment agents. Each environment agent is modeled by a Markov chain whereas the robot is modeled by a finite transition system (in the deterministic case) or Markov decision process (in the stochastic case). Existing results in probabilistic verification are adapted to solve the synthesis problem. To partially address the state explosion issue, we propose an incremental approach where only a small subset of environment agents is incorporated in the synthesis procedure initially and more agents are successively added until we hit the constraints on computational resources. Our algorithm runs in an anytime fashion where the probability that the robot satisfies its specification increases as the algorithm progresses.

The dynamics of multi-agent in nature have been largely studied for a long time to investigate how the aggregation of agents can move smoothly in complex environments without collision. The main insights can be summarized such that the aggregated dynamics of animals and particles can be explained by an individual's simple rules. In a similar vein, we conjecture that such simple rules for vehicle maneuvering can accommodate the fluid flow of traffic and reduce car accidents in highway and urban areas. In this paper, we first show the Reynolds' three rules are applicable to autonomous driving on a single lane. Moreover, we provide additional requirements and algorithms for multiple lanes. Based on these results, we show that the proposed nature-inspired driving maneuver can increase traffic flow by 1) mitigating shockwave at bottlenecks and 2) extending the perception range for better path planning, which requires the support of the vehicle autonomy and wireless communication, respectively. Finally, we prove the feasibility of our work with experiments using multiple UAVs.

Accurate vehicular localization is important for various cooperative vehicle safety (CVS) applications such as collision avoidance, turning assistant, etc. In this paper, we propose a cooperative vehicular distance measurement technique based on the sharing of GPS pseudorange measurements and a weighted least squares method. The classic double difference pseudorange solution, which was originally designed for high-end survey level GPS systems, is adapted to low-end navigation level GPS receivers for its wide availability in ground vehicles. The Carrier to Noise Ratio (CNR) of raw pseudorange measurements are taken into account for noise mitigation. We present a Dedicated Short Range Communications (DSRC) based mechanism to implement the exchange of pseudorange information among neighboring vehicles. As demonstrated in field tests, our proposed technique increases the accuracy of the distance measurement significantly compared with the distance obtained from the GPS fixes.

Formal methods for task management for human operators are gathering increasing attention to improve efficiency of human-in-the-loop systems. In this paper, we consider a novel dynamical queue approach to intelligent task management for human operators. We consider a model of a dynamical queue, where the service time depends on the server utilization history. The proposed queueing model is motivated by, but not restricted to, widely accepted empirical laws describing human performance as a function of mental arousal. The focus of the paper is to characterize the throughput of the dynamical queue and design corresponding maximally stabilizing task release control policies, assuming deterministic arrivals. We focus extensively on threshold policies that release a task to the server only when the server state is less than a certain threshold. When every task brings in the same deterministic amount of work, we give an exact characterization of the throughput and show that an appropriate threshold policy is maximally stabilizing. The technical approach exploits the optimality of the one-task equilibria class associated with the server dynamics. When the amount of work associated with the tasks is an independent identically distributed (i.i.d.) random variable with finite support, we show that the maximum throughput increases in comparison to the case where the tasks have the same deterministic amount of work. Finally, we provide preliminary empirical evidence in support of the applicability of the proposed approach to systems with human operators.

A genetic algorithm that utilizes process algebra for coding of solution chromosomes and for defining evolutionary based operators is presented. The algorithm is applicable to mission planning and optimization problems. As an example the high level mission planning for a cooperative group of uninhabited aerial vehicles is investigated. The mission planning problem is cast as an assignment problem, and solutions to the assignment problem are given in the form of chromosomes that are manipulated by evolutionary operators. The evolutionary operators of crossover and mutation are formally defined using the process algebra methodology, along with specific algorithms needed for their execution. The viability of the approach is investigated using simulations and the effectiveness of the algorithm is shown in small, medium, and large scale problems.

The Rapidly-exploring Random Tree (RRT) algorithm, based on incremental sampling, efficiently computes motion plans. Although the RRT algorithm quickly produces candidate feasible solutions, it tends to converge to a solution that is far from optimal. Practical applications favor "anytime" algorithms that quickly identify an initial feasible plan, then, given more computation time available during plan execution, improve the plan toward an optimal solution. This paper describes an anytime algorithm based on the RRT* which (like the RRT) finds an initial feasible solution quickly, but (unlike the RRT) almost surely converges to an optimal solution. We present two key extensions to the RRT% committed trajectories and branch-and-bound tree adaptation, that together enable the algorithm to make more efficient use of computation time online, resulting in an anytime algorithm for real-time implementation. We evaluate the method using a series of Monte Carlo runs in a high-fidelity simulation environment, and compare the operation of the RRT and RRT* methods. We also demonstrate experimental results for an outdoor wheeled robotic vehicle.

In recent years, the growth of the computational power available in the Central Processing Units (CPUs) of consumer computers has tapered significantly. At the same time, growth in the computational power available in the Graphics Processing Units (GPUs) has remained strong. Algorithms that can be implemented on GPUs today are not only limited to graphics processing, but include scientific computation and beyond. This paper is concerned with massively parallel implementations of incremental sampling-based robot motion planning algorithms, namely the widely-used Rapidly-exploring Random Tree (RRT) algorithm and its asymptotically-optimal counterpart called RRT*. We demonstrate an example implementation of RRT and RRT* motion-planning algorithm for a high-dimensional robotic manipulator that takes advantage of an NVidia CUDA-enabled GPU. We focus on parallelizing the collision-checking procedure, which is generally recognized as the computationally expensive component of sampling-based motion planning algorithms. Our experimental results indicate significant speedup when compared to CPU implementations, leading to practical algorithms for optimal motion planning in high-dimensional configuration spaces.

A desirable property of path planning for robotic manipulation is the ability to identify solutions in a sufficiently short amount of time to be usable. This is particularly challenging for the manipulation problem due to the need to plan over high-dimensional configuration spaces and to perform computationally expensive collision checking procedures. Consequently, existing planners take steps to achieve desired solution times at the cost of low quality solutions. This paper presents a planning algorithm that overcomes these difficulties by augmenting the asymptotically-optimal RRT* with a sparse sampling procedure. With the addition of a collision checking procedure that leverages memoization, this approach has the benefit that it quickly identifies low-cost feasible trajectories and takes advantage of subsequent computation time to refine the solution towards an optimal one. We evaluate the algorithm through a series of Monte Carlo simulations of seven, twelve, and fourteen degree of freedom manipulation planning problems in a realistic simulation environment. The results indicate that the proposed approach provides significant improvements in the quality of both the initial solution and the final path, while incurring almost no computational overhead compared to the RRT algorithm. We conclude with a demonstration of our algorithm for single-arm and dual-arm planning on Willow Garage's PR2 robot.

A trajectory tracking controller based on differential flatness is presented for a nonlinear bicycle model. This controller maps the bicycle dynamics into a point mass located at a center of oscillation with an additional degree of freedom of yaw dynamics. A state transformation is performed that reveals structure in the yaw dynamics resembling a Lie¿nard system. A candidate Lyapunov function inspired by this structure is used to assess the stability of the yaw dynamics while tracking straight-line trajectories and steady turns. The basin of attraction of the controller is limited by actuator constraints and the presence of unstable equilibrium points during turns with high lateral acceleration. The controller properties and the stability of yaw dynamics are demonstrated in simulation.

Recent years have witnessed great advancements in the science and technology of autonomy, robotics, and networking. This paper surveys recent concepts and algorithms for dynamic vehicle routing (DVR), that is, for the automatic planning of optimal multivehicle routes to perform tasks that are generated over time by an exogenous process. We consider a rich variety of scenarios relevant for robotic applications. We begin by reviewing the basic DVR problem: demands for service arrive at random locations at random times and a vehicle travels to provide on-site service while minimizing the expected wait time of the demands. Next, we treat different multivehicle scenarios based on different models for demands (e.g., demands with different priority levels and impatient demands), vehicles (e.g., motion constraints, communication, and sensing capabilities), and tasks. The performance criterion used in these scenarios is either the expected wait time of the demands or the fraction of demands serviced successfully. In each specific DVR scenario, we adopt a rigorous technical approach that relies upon methods from queueing theory, combinatorial optimization, and stochastic geometry. First, we establish fundamental limits on the achievable performance, including limits on stability and quality of service. Second, we design algorithms, and provide provable guarantees on their performance with respect to the fundamental limits.

We present an investigation of dynamic team formation strategies for robot ensembles performing a collection of single and two-robot tasks. Specifically, we consider the abstract “stick and pebble” problem, as a variation of the “stick pulling” problem discussed in the literature. We present a formulation of the dynamic team formation problem that is independent of ensemble size and develop a macroscopic analytical description of the ensemble dynamics. The macroscopic model is then used to determine the optimal teaming strategy for two different performance metrics. We present agent-based simulation results to support the validity of our macroscopic analysis.

In this paper we study a dynamic vehicle routing problem where demands have stochastic deadlines on their waiting times. Specifically, a network of robotic vehicles must service demands whose time of arrival, location and on-site service are stochastic; moreover, once a demand arrives, it remains active for a stochastic amount of time, and then expires. An active demand is successfully serviced when one of the vehicles visits its location before its deadline and provide the required on-site service. The aim is to find the minimum number of vehicles needed to ensure that the steady-state probability that a demand is successfully serviced is larger than a desired value, and to determine the policy the vehicles should execute to ensure that such objective is attained. First, we carefully formulate the problem, and we show its well-posedness by providing some novel ergodic results. Second, we provide a lower bound on the optimal number of vehicles; finally, we analyze two service policies, and we show that one of them is optimal in light load. Simulation results are presented and discussed.

One long-standing challenge in robotics is the realization of mobile autonomous robots able to operate safely in existing human workplaces in a way that their presence is accepted by the human occupants. We describe the development of a multi-ton robotic forklift intended to operate alongside human personnel, handling palletized materials within existing, busy, semi-structured outdoor storage facilities. The system has three principal novel characteristics. The first is a multimodal tablet that enables human supervisors to use speech and pen-based gestures to assign tasks to the forklift, including manipulation, transport, and placement of palletized cargo. Second, the robot operates in minimally-prepared, semi-structured environments, in which the forklift handles variable palletized cargo using only local sensing (and no reliance on GPS), and transports it while interacting with other moving vehicles. Third, the robot operates in close proximity to people, including its human supervisor, other pedestrians who may cross or block its path, and forklift operators who may climb inside the robot and operate it manually. This is made possible by novel interaction mechanisms that facilitate safe, effective operation around people. We describe the architecture and implementation of the system, indicating how real-world operational requirements motivated the development of the key subsystems, and provide qualitative and quantitative descriptions of the robot operating in real settings.

This paper addresses the problem of autonomous manipulation of a priori unknown palletized cargo with a robotic lift truck (forklift). Specifically, we describe coupled perception and control algorithms that enable the vehicle to engage and place loaded pallets relative to locations on the ground or truck beds. Having little prior knowledge of the objects with which the vehicle is to interact, we present an estimation framework that utilizes a series of classifiers to infer the objects' structure and pose from individual LIDAR scans. The classifiers share a low-level shape estimation algorithm that uses linear programming to robustly segment input data into sets of weak candidate features. We present and analyze the performance of the segmentation method, and subsequently describe its role in our estimation algorithm. We then evaluate the performance of a motion controller that, given an estimate of a pallet's pose, is employed to safely engage each pallet. We conclude with a validation of our algorithms for a set of real-world pallet and truck interactions.

The most widely applied resource allocation strategy is to balance, or equalize, the total workload assigned to each resource. In mobile multi-agent systems, this principle directly leads to equitable partitioning policies in which (i) the workspace is divided into subregions of equal measure, (ii) there is a bijective correspondence between agents and subregions, and (iii) each agent is responsible for service requests originating within its own subregion. In this paper, we provide the first distributed algorithm that provably allows m agents to converge to an equitable partition of the workspace, from any initial configuration, i.e., globally. Our approach is related to the classic Lloyd algorithm, and provides novel insights into the properties of power diagrams. Simulation results are presented and discussed.

This paper provides a detailed analysis of the motion planning subsystem for the MIT DARPA Urban Challenge vehicle. The approach is based on the Rapidly-exploring Random Trees (RRT) algorithm. The purpose of this paper is to present the numerous extensions made to the standard RRT algorithm that enable the on-line use of RRT on robotic vehicles with complex, unstable dynamics and significant drift, while preserving safety in the face of uncertainty and limited sensing. The paper includes numerous simulation and race results that clearly demonstrate the effectiveness of the planning system.

Sampling-based nonholonomic and kinodynamic planning iteratively constructs solutions with sampled controls. A constructed trajectory is returned as an acceptable solution if its ldquogaps,rdquo including discontinuities within the trajectory and mismatches between the terminal and goal states, are within a given gap tolerance. For a given coarseness in the sampling of the control space, finding a trajectory with a small gap tolerance might be either impossible or extremely expensive. In this paper, we propose an efficient trajectory perturbation method, which complements existing steering and perturbation methods, enabling these sampling-based algorithms to quickly obtain solutions by reducing large gaps in constructed trajectories. Our method uses system symmetry, e.g., invariance of dynamics with respect to certain state transformations, to achieve efficient gap reduction by evaluating trajectory final state with a constant-time operation, and, naturally, generating the admissible perturbed trajectories. Simulation results demonstrate dramatic performance improvement for unidirectional, bidirectional, and PRM-based sampling-based algorithms with the proposed enhancement with respect to their basic counterparts on different systems: one with the second-order dynamics, one with nonholonomic constraints, and one with two different modes.

In this paper, we propose a novel policy for steering multiple vehicles between assigned start and goal configurations, ensuring collision avoidance. The policy rests on the assumption that all agents are cooperating by implementing the same traffic rules. However, the policy is completely decentralized, as each agent decides its own motion by applying those rules only on the locally available information, and scalable, in the sense that the amount of information processed by each agent and the computational complexity of the algorithms do not increase with the number of agents in the scenario. The proposed policy applies to systems in which new vehicles may enter the scene and start interacting with existing ones at any time, while others may leave. Under mild conditions on the initial configurations, the policy is shown to be safe, i.e., it guarantees collision avoidance throughout the system evolution. In the paper, conditions are discussed on the desired configurations of agents, under which the ultimate convergence of all vehicles to their goals can also be guaranteed. To show that such conditions are actually necessary and sufficient, which turns out to be a challenging liveness-verification problem for a complex hybrid automaton, we employ a probabilistic verification method. The paper finally presents and discusses simulations for systems of several tens of vehicles, and reports on some experimental implementation showing the practicality of the approach.

The roller racer, an undulatory locomotion system, is a toy which can be propelled forward by sitting on it and only oscillating the steering handle. A nonholonomic dynamic model and controllability analysis of the roller racer was first published by Krishnaprasad and Tsakiris in 1998. The model is derived from the usual assumption that all the wheels obey sticking (non-slipping) constraints, i.e., rolling without slipping. Controllability analysis shows that under these assumptions, the roller racer cannot be stopped once started. Yet physical prototypes do not exhibit this characteristic. In this paper, a high-fidelity model of the roller racer is presented by considering the finite static friction between the wheels and the ground, i.e., slipping will occur when constraint force exceeds the maximal allowable frictional force. It is proved that the system could be stopped from any state with only the steering angle control. Furthermore, based on group symmetry and motion primitives, a planner is designed to achieve motions between any two given positions and orientations with zero velocities. Experiments also show that front wheel slipping stops the system faster than joint frictions

In this paper, we consider a decentralized cooperative control policy proposed recently for steering multiple nonholonomic vehicles between assigned start and goal configurations while avoiding collisions. The policy is known to ensure safety (i.e., collision avoidance) for an arbitrarily large number of vehicles, if initial configurations satisfy certain conditions. The method is highly scalable, and effective solutions can be obtained for several tens of autonomous agents. On the other hand, the liveness properties of the policy, i.e. the capability of negotiating a solution in finite time, are not completely understood yet. In this paper, we introduce a condition on the final vehicle configurations, which we conjecture to be necessary and sufficient for guaranteeing liveness. We prove the necessity by a constructive method. Because of the overwhelming complexity of proving the sufficiency of such condition, we assess the correctness of the conjecture in probability through the analysis of the results of a large number of randomized experiments

The TRIKKE is a three-wheeled, human-powered scooter that can be propelled by a combination of cyclic motion of its handlebar and swaying motion of the rider. This paper addresses the modeling, dynamics and control of the TRIKKE and the development of a robotic platform called the ROBOTRIKKE that is derived from similar principles. The TRIKKE can be modeled as a modified roller-racer with an unstable steering arrangement. The model of the TRIKKE reduces to the roller-racer [8] in the absence of this steering arrangement. We prove that under certain conditions on the geometric parameters of the system, the TRIKKE and roller-racer systems cannot be stopped after motion starting from rest using the steering control as the sole input. As a consequence, the ideal model is severely limited from the point of view of controllability. We demonstrate the validity of our model through comparison with experimental measurements on a small-scale robotic prototype of the TRIKKE. We present closed-loop control results for tracking (on average) a straight line trajectory using visual feedback from an overhead camera.

In this paper, we introduce an approach for the efficient solution of motion-planning problems for time-invariant dynamical control systems with symmetries, such as mobile robots and autonomous vehicles, under a variety of differential and algebraic constraints on the state and on the control inputs. Motion plans are described as the concatenation of a number of well-defined motion primitives, selected from a finite library. Rules for the concatenation of primitives are given in the form of a regular language, defined through a finite-state machine called a Maneuver Automaton. We analyze the reachability properties of the language, and present algorithms for the solution of a class of motion-planning problems. In particular, it is shown that the solution of steering problems for nonlinear dynamical systems with symmetries and invariant constraints can be reduced to the solution of a sequence of kinematic inversion problems. A detailed example of the application of the proposed approach to motion planning for a small aerobatic helicopter is presented.

Although sampling-based planning algorithms have been extensively used to approximately solve motion planning problems with differential constraints, gaps usually appear in their solution trajectories due to various factors. Higher precision may be requested, but as we show in this paper, this dramatically increases the computational cost. In practice, this could mean that a solution would not be found in a reasonable amount of time. In this paper, we substantially improve the performance of an RRT-based algorithm by planning low precision solutions, and then refining their quality by employing a gap reduction technique that exploits group symmetries of the system to avoid costly numerical integrations. This technique also allows PRMs to be extended to problems with differential constraints, even when no high-quality steering method exists.

In this paper we consider improving the quantity and quality of data collected and sent to a sink over the lifetime of a network of mobile sensors. The positions of the sensors and the routing strategy chosen are the variables in our problem. The original problem is a multi-objective non-convex optimization problem and we believe it to be tough to solve. The approach taken in this paper is to break down the original problem into sub-problems and develop an iterative scheme to optimize both the quantities. We propose three sub-problems. First, we optimize the way (obtain flows) the data is sent to the sink for a fixed placement of the nodes by solving a linear program (work on this has already been done in the past by others). Once flows have been obtained, they are kept constant and the nodes are then moved in a way such that the lifetime is further improved, keeping the maximum distortion error less than or equal to what it is for the initial node placement. Then for the new node distribution with a better lifetime, we decrease the maximum distortion error keeping the lifetime greater than or equal as compared to the starting configuration. Centralized and decentralized iterative schemes are presented using these subproblems that monotonically improve the lifetime data gathering and reduce maximum distortion error at each step.

We address the problem of eliminating gaps in paths that are constructed by some nonholonomic and kinodynamic motion planning algorithms. In many of these algorithms, control inputs at each planning step are chosen from a finite set, obtained from discretization of the available control set. While this approach is attractive for computational reasons, it can generate gaps, or discontinuities, either between path segments or between the final state and the desired goal. For the purpose of reducing gaps, the original control set and continuous time interval can be utilized, and perturbations may be applied to incrementally optimize the gap error while respecting collision constraints. By exploiting Lie group symmetries, which emerge in a broad class of robot systems, we are able to avoid costly numerical integrations that usually occur in each step of gradient-based optimization techniques. It is hoped that the approach can ultimately lead to faster planning algorithms by allowing coarser discretizations of time and the available input set, with the understanding that later refinements can be made efficiently.