Deep reinforcement learning (DRL) provides a promising way for intelligent agents (e.g., autonomous vehicles) to learn to navigate complex scenarios. However, DRL with neural networks as function approximators is typically considered a black box with little explainability and often suffers from suboptimal performance, especially for autonomous navigation in highly interactive multi-agent environments. To address these issues, we propose three auxiliary tasks with spatio-temporal relational reasoning and integrate them into the standard DRL framework, which improves the decision making performance and provides explainable intermediate indicators. We propose to explicitly infer the internal states (i.e., traits and intentions) of surrounding agents (e.g., human drivers) as well as to predict their future trajectories in the situations with and without the ego agent through counterfactual reasoning. These auxiliary tasks provide additional supervision signals to infer the behavior patterns of other interactive agents. Multiple variants of framework integration strategies are compared. We also employ a spatio-temporal graph neural network to encode relations between dynamic entities, which enhances both internal state inference and decision making of the ego agent. Moreover, we propose an interactivity estimation mechanism based on the difference between predicted trajectories in these two situations, which indicates the degree of influence of the ego agent on other agents. To validate the proposed method, we design an intersection driving simulator based on the Intelligent Intersection Driver Model (IIDM) that simulates vehicles and pedestrians. Our approach achieves robust and state-of-the-art performance in terms of standard evaluation metrics and provides explainable intermediate indicators (i.e., internal states, and interactivity scores) for decision making.

Multi-agent reinforcement learning (MARL) provides an efficient way for simultaneously learning policies for multiple agents interacting with each other. However, in scenarios requiring complex interactions, existing algorithms can suffer from an inability to accurately anticipate the influence of self-actions on other agents. Incorporating an ability to reason about other agents' potential responses can allow an agent to formulate more effective strategies. This paper adopts a recursive reasoning model in a centralized-training-decentralized-execution framework to help learning agents better cooperate with or compete against others. The proposed algorithm, referred to as the Recursive Reasoning Graph (R2G), shows state-of-the-art performance on multiple multi-agent particle and robotics games.

Deep reinforcement learning (DRL) provides a promising way for learning navigation in complex autonomous driving scenarios. However, identifying the subtle cues that can indicate drastically different outcomes remains an open problem with designing autonomous systems that operate in human environments. In this work, we show that explicitly inferring the latent state and encoding spatial-temporal relationships in a reinforcement learning framework can help address this difficulty. We encode prior knowledge on the latent states of other drivers through a framework that combines the reinforcement learner with a supervised learner. In addition, we model the influence passing between different vehicles through graph neural networks (GNNs). The proposed framework significantly improves performance in the context of navigating T-intersections compared with state-of-the-art baseline approaches.

This paper proposes a discretionary lane selection algorithm. In particular, highway driving is considered as a targeted scenario, where each lane has a different level of traffic flow. When lane-changing is discretionary, it is advised not to change lanes unless highly beneficial, e.g., reducing travel time significantly or securing higher safety. Evaluating such “benefit” is a challenge, along with multiple surrounding vehicles in dynamic speed and heading with uncertainty. We propose a realtime lane-selection algorithm with careful cost considerations and with modularity in design. The algorithm is a search-based optimization method that evaluates uncertain dynamic positions of other vehicles under a continuous time and space domain. For demonstration, we incorporate a state-of-the-art motion planner framework (Neural Networks integrated Model Predictive Control) under a CARLA simulation environment.

Traditional planning and control methods could fail to find a feasible trajectory for an autonomous vehicle to execute amongst dense traffic on roads. This is because the obstacle-free volume in spacetime is very small in these scenarios for the vehicle to drive through. However, that does not mean the task is infeasible since human drivers are known to be able to drive amongst dense traffic by leveraging the cooperativeness of other drivers to open a gap. The traditional methods fail to take into account the fact that the actions taken by an agent affect the behaviour of other vehicles on the road. In this work, we rely on the ability of deep reinforcement learning to implicitly model such interactions and learn a continuous control policy over the action space of an autonomous vehicle. The application we consider requires our agent to negotiate and open a gap in the road in order to successfully merge or change lanes. Our policy learns to repeatedly probe into the target road lane while trying to find a safe spot to move in to. We compare against two model-predictive control-based algorithms and show that our policy outperforms them in simulation. As part of this work, we introduce a benchmark for driving in dense traffic for use by the community.

Estimating statistical uncertainties allows autonomous agents to communicate their confidence during task execution and is important for applications in safety-critical domains such as autonomous driving. In this work, we present the uncertainty-aware imitation learning (UAIL) algorithm for improving end-to-end control systems via data aggregation. UAIL applies Monte Carlo Dropout to estimate uncertainty in the control output of end-to-end systems, using states where it is uncertain to selectively acquire new training data. In contrast to prior data aggregation algorithms that force human experts to visit sub-optimal states at random, UAIL can anticipate its own mistakes and switch control to the expert in order to prevent visiting a series of sub-optimal states. Our experimental results from simulated driving tasks demonstrate that our proposed uncertainty estimation method can be leveraged to reliably predict infractions. Our analysis shows that UAIL outperforms existing data aggregation algorithms on a series of benchmark tasks.

In a multi-agent setting, the optimal policy of a single agent is largely dependent on the behavior of other agents. We investigate the problem of multi-agent reinforcement learning, focusing on decentralized learning in non-stationary domains for mobile robot navigation. We identify a cause for the difficulty in training non-stationary policies: mutual adaptation to sub-optimal behaviors, and we use this to motivate a curriculum-based strategy for learning interactive policies. The curriculum has two stages. First, the agent leverages policy gradient algorithms to learn a policy that is capable of achieving multiple goals. Second, the agent learns a modifier policy to learn how to interact with other agents in a multi-agent setting. We evaluated our approach on both an autonomous driving lane-change domain and a robot navigation domain.

In order to drive safely and efficiently under merging scenarios, autonomous vehicles should be aware of their surroundings and make decisions by interacting with other road participants. Moreover, different strategies should be made when the autonomous vehicle is interacting with drivers having different level of cooperativeness. Whether the vehicle is on the merge-lane or main-lane will also influence the driving maneuvers since drivers will behave differently when they have the right-of-way than otherwise. Many traditional methods have been proposed to solve decision making problems under merging scenarios. However, these works either are incapable of modeling complicated interactions or require implementing hand-designed rules which cannot properly handle the uncertainties in real-world scenarios. In this paper, we proposed an interaction-aware decision making with adaptive strategies (IDAS) approach that can let the autonomous vehicle negotiate the road with other drivers by leveraging their cooperativeness under merging scenarios. A single policy is learned under the multi-agent reinforcement learning (MARL) setting via the curriculum learning strategy, which enables the agent to automatically infer other drivers' various behaviors and make decisions strategically. A masking mechanism is also proposed to prevent the agent from exploring states that violate common sense of human judgment and increase the learning efficiency. An exemplar merging scenario was used to implement and examine the proposed method.

Navigating urban environments represents a complex task for automated vehicles. They must reach their goal safely and efficiently while considering a multitude of traffic participants. We propose a modular decision making algorithm to autonomously navigate intersections, addressing challenges of existing rule-based and reinforcement learning (RL) approaches. We first present a safe RL algorithm relying on a model-checker to ensure safety guarantees. To make the decision strategy robust to perception errors and occlusions, we introduce a belief update technique using a learning based approach. Finally, we use a scene decomposition approach to scale our algorithm to environments with multiple traffic participants. We empirically demonstrate that our algorithm outperforms rule-based methods and reinforcement learning techniques on a complex intersection scenario.

Occupancy maps offer a useful representation of the environment for applications in automated driving and robotics. If created from 3D lidar scanners, they can be very accurate. Traditional static occupancy mapping methods are not able to represent a changing environment. In this paper, we present a novel dynamic occupancy mapping (DOM) algorithm. Inspired by the phase congruency idea from computer vision, it has an intuitive formulation and yet is effective in practice. In addition, our framework provides solutions to several common challenges during occupancy mapping, such as multi-lidar fusion and ground estimation. Finally, we use several experiments to quantitatively evaluate the quality of DOM's output and our algorithm runs in real-time (10Hz).

Autonomous driving in urban areas requires avoiding other road users with only partial observability of the environment. Observations are only partial because obstacles can occlude the field of view of the sensors. The problem of robust and efficient navigation under uncertainty can be framed as a partially observable Markov decision process (POMDP). In order to bypass the computational cost of scaling the formulation to avoiding multiple road users, this paper demonstrates a decomposition method that leverages the optimal avoidance strategy for a single user. We evaluate the performance of two POMDP solution techniques augmented with the decomposition method for scenarios involving a pedestrian crosswalk and an intersection.

Providing an efficient strategy to navigate safely through unsignaled intersections is a difficult task that requires determining the intent of other drivers. We explore the effectiveness of Deep Reinforcement Learning to handle intersection problems. Using recent advances in Deep RL, we are able to learn policies that surpass the performance of a commonly-used heuristic approach in several metrics including task completion time and goal success rate and have limited ability to generalize. We then explore a system's ability to learn active sensing behaviors to enable navigating safely in the case of occlusions. Our analysis, provides insight into the intersection handling problem, the solutions learned by the network point out several shortcomings of current rule-based methods, and the failures of our current deep reinforcement learning system point to future research directions.

Driving is a social activity: drivers often indicate their intent to change lanes via motion cues. We consider mixed-autonomy traffic where a Human-driven Vehicle (HV) and an Autonomous Vehicle (AV) drive together. We propose a planning framework where the degree to which the AV considers the other agent's reward is controlled by a selfishness factor. We test our approach on a simulated two-lane highway where the AV and HV merge into each other's lanes. In a user study with 21 subjects and 6 different selfishness factors, we found that our planning approach was sound and that both agents had less merging times when a factor that balances the rewards for the two agents was chosen. Our results on double lane merging suggest it to be a non-zero-sum game and encourage further investigation on collaborative decision making algorithms for mixed-autonomy traffic.

There have been numerous advances in reinforcement learning, but the typically unconstrained exploration of the learning process prevents the adoption of these methods in many safety critical applications. Recent work in safe reinforcement learning uses idealized models to achieve their guarantees, but these models do not easily accommodate the stochasticity or high-dimensionality of real world systems. We investigate how prediction provides a general and intuitive framework to constraint exploration, and show how it can be used to safely learn intersection handling behaviors on an autonomous vehicle.

This study presents the preliminary attempt to investigate the usage of driver physiology signals, including electrocardiography (ECG) and respiration wave signals, to predict driving maneuvers. While most studies on driving maneuver prediction uses direct measurements from vehicle or road scene, we believe the mental state changes from the driver when making plans for maneuver can be reflected from the physiological signals. We extract both time and frequency domain features from the physiological signals, and use them as the features to predict the drivers' future maneuver. We formulate the prediction of driver maneuver as a multi-class classification problem by using the features extracted from signal before the driving maneuvers. The multi classes correspond to various types of driving maneuvers including Start, Stop, Lane Switch and Turn. We use the support vector machine (SVM) as the classifier, and compare the performance of using both physiological and car signals (CAN bus) with the baseline classifier that is trained with only car signal. An improved performance is observed when using the physiological features with 0.04 in F-score on average. This improvement is more obvious as the prediction is made earlier.

Current pedestrian collision warning systems use either auditory alarms or visual symbols to inform drivers. These traditional approaches cannot tell the driver where the detected pedestrians are located, which is critical for the driver to respond appropriately. To address this problem, we introduce a new driver interface taking advantage of a volumetric head-up display (HUD). In our experimental user study, sixteen participants drove a test vehicle in a parking lot while braking for crossing pedestrians using different interface designs on the HUD. Our results showed that spatial information provided by conformal graphics on the HUD resulted in not only better driver performance but also smoother braking behavior as compared to the baseline.

Augmented reality (AR) is an interface that can potentially provide more intuitive and immersive experiences, particularly for automotive applications. In this paper we present the Personal Navi, a vehicular AR navigational aid designed for use with a see-thru 3D volumetric Head Up Display (HUD). In one study, we found that the Personal Navi visuals helped participants recognize turn locations earlier than when provided with conventional navigation aids alone. The interface also helped keep users' eyes up and fixated on the driving environment more. In a second study, we tested participants' depth perception of AR visuals provided with our prototype 3D-HUD. We displayed the same visuals with a fixed focal depth display (2D-HUD) and found that for applications such as Personal Navi, where the spatial location of AR visuals are an important component of the interface, a dynamically adjustable focal plane (3D-HUD) is necessary for proper registration. We argue that AR-based HUD navigational aids should be implemented only with 3D-HUDs because of inferior depth perception with 2D-HUDs.

In this work, we introduce a real-time driver activity recognition method which takes a sequence of depth images as input and outputs an activity class among a predetermined set of driver activities. A classification algorithm called Random Forests is employed and further enhanced by a unique state based inference system to reduce initial classifier errors. For example, frequent changes in driver activities are penalized so as to stabilize the output. The cost of activity change is decided by a state inference system which takes both temporal and spatial coherence into account. The paper will introduce the training system, explain the state inference system and the cost based penalty calculation. Finally we will discuss the results and future work.

With the capability of fast, wireless communication, combined with cloud and location-based services, modern drivers can potentially access a wide variety of information about their automobile's environment. This paper presents a system for information query by the driver by using a simple pointing mechanism, combined with visual feedback in the form of a 3-D Head-up Display (3D-HUD). Because of its 3-D properties, the HUD can also be used for Augmented Reality (AR) as it allows physical elements in the driver's field of view to be annotated with computer graphics. The combination of simple natural user input tailored for the constraints of the driver with a see-thru 3D-HUD allows drivers to query information while minimizing visual and manual distraction.

This paper introduces a kinematically constrained closed loop inverse kinematics algorithm for motion control of robots or other articulated rigid body systems. The proposed strategy utilizes gradients of collision and joint limit potential functions to arrive at an appropriate weighting matrix to penalize and dampen motion approaching constraint surfaces. The method is particularly suitable for self collision avoidance of highly articulated systems which may have multiple collision points among several segment pairs. In that respect, the proposed method has a distinct advantage over existing gradient projection based methods which rely on numerically unstable null-space projections when there are multiple intermittent constraints. We also show how this approach can be augmented with a previously reported method based on redirection of constraints along virtual surface manifolds. The hybrid strategy is effective, robust, and does not require parameter tuning. The efficacy of the proposed algorithm is demonstrated for a self collision avoidance problem where the reference motion is obtained from human observations. We show simulation and experimental results on the humanoid robot ASIMO.

Many advanced motion control strategies developed in robotics use captured human motion data as valuable source of examples to simplify the process of programming or learning complex robot motions. Direct and online control of robots from observed human motion has several inherent challenges. The most important may be the representation of the large number of mechanical degrees of freedom involved in the execution of movement tasks. Attempting to map all such degrees of freedom from a human to a humanoid is a formidable task from an instrumentation and sensing point of view. More importantly, such an approach is incompatible with mechanisms in the central nervous system which are believed to organize or simplify the control of these degrees of freedom during motion execution and motor learning phase. Rather than specifying the desired motion of every degree of freedom for the purpose of motion control, it is important to describe motion by low dimensional motion primitives that are defined in Cartesian (or task) space. In this paper, we formulate the human to humanoid retargeting problem as a task space control problem. The control objective is to track desired task descriptors while satisfying constraints such as joint limits, velocity limits, collision avoidance, and balance. The retargeting algorithm generates the joint space trajectories that are commanded to the robot. We present experimental and simulation results of the retargeting control algorithm on the Honda humanoid robot ASIMO.

Transferring motion from a human demonstrator to a humanoid robot is an important step toward developing robots that are easily programmable and that can replicate or learn from observed human motion. The so called motion retargeting problem has been well studied and several off-line solutions exist based on optimization approaches that rely on pre-recorded human motion data collected from a marker-based motion capture system. From the perspective of human robot interaction, there is a growing interest in online and marker-less motion transfer. Such requirements have placed stringent demands on retargeting algorithms and limited the potential use of off-line and pre-recorded methods. To address these limitations, we present an online task space control theoretic retargeting formulation to generate robot joint motions that adhere to the robot’s joint limit constraints, self-collision constraints, and balance constraints. The inputs to the proposed method include low dimensional normalized human motion descriptors, detected and tracked using a vision based feature detection and tracking algorithm. The proposed vision algorithm does not rely on markers placed on anatomical landmarks, nor does it require special instrumentation or calibration. The current implementation requires a depth image sequence, which is collected from a single time of flight imaging device. We present online experimental results of the entire pipeline on the Honda humanoid robot - ASIMO.

We present a human-robot interactive scenario consisting of a memory card game between Hondapsilas humanoid robot ASIMO and a human player. The game features perception exclusively through ASIMOpsilas on-board cameras and both reactive and proactive behaviors specific to different situational contexts in the memory game. ASIMO is able to build a dynamic environmental map of relevant objects in the game such as the table and card layout as well as understand activities from the player such as pointing at cards, flipping cards and removing them from the table. Our system architecture, called the Cognitive Map, treats the memory game as a multi-agent system, with modules acting independently and communicating with each other via messages through a shared blackboard system. The game behavior module can model game state and contextual information to make decisions based on different pattern recognition modules. Behavior is then sent through high-level command interfaces to be resolved into actual physical actions by the robot via a multi-modal communication module. The experience gained in modeling this interactive scenario will allow us to reuse the architecture to create new scenarios and explore new research directions in learning how to respond to new interactive situations.

This paper presents a method for pedestrian detection and tracking using a single night-vision video camera installed on the vehicle. To deal with the nonrigid nature of human appearance on the road, a two-step detection/tracking method is proposed. The detection phase is performed by a support vector machine (SVM) with size-normalized pedestrian candidates and the tracking phase is a combination of Kalman filter prediction and mean shift tracking. The detection phase is further strengthened by information obtained by a road-detection module that provides key information for pedestrian validation. Experimental comparisons (e.g., grayscale SVM recognition versus binary SVM recognition and entire-body detection versus upper-body detection) have been carried out to illustrate the feasibility of our approach.

A method is presented for extracting pedestrian information from an image sequence taken by a monocular camera. The method makes use of hybrid sensing of depth and gray information and it is shown to work well in an indoor environment. A split-and-merge strategy is proposed to process depth data for object and human detection. Furthermore, human tracking and event detection are also presented to recognize simple behavior such as hand-shaking. This method does not use background subtraction, and therefore it is applicable for scenes taken from mobile platforms. Experimental results are presented to validate our approach.

Non-intrusive methods based on active remote IR illumination for eye tracking are important for many applications of vision-based man-machine interaction. One problem that has plagued those methods is their sensitivity to lighting condition change. This tends to significantly limit their scope of application. In this paper, we present a new real-time eye detection and tracking methodology that works under variable and realistic lighting conditions. Based on combining the bright-pupil effect resulted from IR light and the conventional appearance-based object recognition technique, our method can robustly track eyes when the pupils are not very bright due to significant external illumination interferences. The appearance model is incorporated in both eyes detection and tracking via the use of support vector machine and the mean shift tracking. Additional improvement is achieved from modifying the image acquisition apparatus including the illuminator and the camera.

We present the system overview and integration of the ASIMO autonomous robot that can function successfully in indoor environments. The first model of ASIMO is already being leased to companies for receptionist work. In this paper, we describe the new capabilities that we have added to ASIMO. We explain the structure of the robot system for intelligence, integrated subsystems on its body, and their new functions. We describe the behavior-based planning architecture on ASIMO and its vision and auditory system. We describe its gesture recognition system, human interaction and task performance. We also discuss the external online database system that can be accessed using internet to retrieve desired information, the management system for receptionist work, and various function demonstrations.

Intelligent Transportation Systems (ITS) have become a focus for many countries. To achieve ITS, Inter Vehicle Communication (IVC) is required for the exchange and distribution of data such as congestion or emergency information. If this communication can be done without fixed infrastructure, the systems can be deployed quickly and on a larger scale. Ad hoc networking technologies are one such technology to achieve IVC. However, if generic ad hoc network solutions are applied directly to IVC, performance can degrade quickly as the system scales particularly for broadcast type messages. In this paper we propose two new broadcast protocols that reduce bandwidth required for broadcast communication by taking advantage of a vehicle's highly directional movement and Global Positioning Information. To show the performance of our new protocols, we compare our approach with generic ad hoc broadcasting techniques. Our results show that it is possible to achieve several hundred percent improvement of bandwidth utilization with very slight sacrifice of reachability.

A method for shape comparison is presented using shape deformation. Unlike many other approaches to shape similarity which use local characteristics such as curvature, our approach captures global features of the shapes being compared and is less sensitive to uneven noise. The problem is cast into polygon-to-polygon deformation (i.e., homotopic deformation) and a new shape signature is introduced based on deformation. A polygon deformation algorithm is presented which runs in O(nk+n logn) time, where n is the number of vertices in the polygonal shapes and k is an index to indicate how the target shape is convoluted. Experimental results are included to demonstrate the feasibility of our approach.

Methods are presented for cutting the surface of a polygonal shape that is homeomorphic to the torus. A number of issues are discussed as to how to find loops of a desired characteristic on the surface of a polyhedrally-defined torus and how to cut the torus into two parts by using the loops discovered. A method for finding a homeomorphism for toroidal surfaces is also described, which is important for shape transformation and texture mapping in graphics.

An image warping method is presented that deforms an image continuously without foldover while observing a given set of trajectories of feature elements. Any intermediate image during the morph is homeomorphic to the initial image and the morphing process is a homotopy. The method permits points, line segments, and polygons to be included as features in the image. Techniques are described to make the deformation process smooth in spatial as well as temporal dimensions. An experimental result is included to demonstrate the feasibility of our approach and complexity of the algorithm is analyzed. Morphing between images that are topologically unequivalent is also briefly discussed.

The measurement, analysis and visualization of plant growth is of primary interest to plant biologists. We are developing software tools to support such investigations. There are two parts in this investigation, namely growth visualization of (i) a plant root and (ii) a plant stem. For both domains, the input data is a stream of images taken by cameras. The tools being developed make it possible to measure various time-varying quantities, such as differential growth. For both domains, the plant is modeled by using flexible templates to represent non-rigid motions.

Route planning for mobile robots in time-dependent networks is investigated. The mobile robot is constrained to move in a prespecified network of roads. The environment contains a set of moving obstacles which are not necessarily constrained to move along arcs of the network and whose motions are assumed to be known. Due to dynamic objects in the environment, connectivity in the network changes over time, i.e., the network is time-dependent. Given such an environment, a method is presented to find a collision-free route in the network that takes the mobile robot from a given start node to a destination node in minimum time. Our method generates a time-minimum path for all time intervals during which the destination node is reachable. The problem is solved by a two-level graph search: (1) path search using a space-time spanning tree, and (2) path search in a time-dependent network. Algorithms for the two subproblems are presented and execution time of the algorithms is analyzed.>

A method is investigated for finding a collision-free path for a mobile robot with a few degrees of freedom in a time-varying domain. The environment contains a set of obstacles with arbitrary known motion patterns. In a time-varying environment, paths are time-dependent, i.e., a path needs to be specified as a function of time, since connectivity in the environment changes over time. Given a time-varying environment, a start time, and a start location, a method is presented for finding a collision-free path from start to goal points for a finite-size robot subject to a speed bound. Our method makes use of a heuristic approach based on a transient pixel representation.>

Motion planning amidst moving obstacles in three dimensions is considered. Each obstacle is a polyhedron in three dimensions that moves with a constant speed at a fixed direction. Three basic properties are established for time-minimal motions in three dimensions amidst slowly moving obstacles. Representing moving three-dimensional objects with full generality would require space-time for four dimensions. The discussion is based on the idea of three-dimensional collision fronts and does not make explicit use of the time dimension. This makes it possible to treat the problem as in the case of stationary obstacles.

The problem of navigation of cooperative multiple heterogeneous mobile robots is investigated. The mobile robots vary in size and their capabilities in terms of speeds to navigate through the region and sensor ranges to acquire information about the region. The robots are assumed to have sufficient memory to store the map and to be able to communicate with each other. An algorithm is presented for plane sweep by cooperative multiple mobile robots. The authors' approach makes use of an occupancy grid and the robots sensors are to sweep all pixels of the grid. The algorithm is discussed in detail and its feasibility is demonstrated by simulation results for the case of two cooperating mobile robots.

A method is presented to detect index corruption and pointer corruption in B/sup +/-trees. The method uses the semantic information of indices and requires no extra pointers to be added to the data structure. Previous research on the robustness on B-trees has considered index corruption and pointer corruption separately and required extra pointers to be added to the data structure to achieve detectability, and correctability. The proposed method can detect and identify a single semantic or structural error.>

The author discusses important class of dynamic obstacles, that is, obstacles that appear and disappear in the environment. This formulation allows modeling of a number of time-varying situations that can arise in application domains. For example, a motion can be planned in an environment where an agent rearranges the environment by picking up an object and placing it back at another location in the same environment. An algorithm is presented to generate a motion in such a dynamic domain. The algorithm runs in O(n/sup 3/ log n) time, where n is the total number of vertices in the environment.>

Route planning for mobile robots among moving obstacles is studied. Unlike most of the work in motion planning amidst moving obstacles, our mobile robots are constrained to move in a prespecified network of roads. Given an environment containing moving obstacles, &,art and destination nodes in the network, and a start time, the method is presented to find a collision-free route in the network that takes the mobile robot from the start node to the destination time in minimum time, if there is one. The problem is divided into two subproblems: (i) one-dimensional path planning amidst dynamic obstacles and (ii) path search in the network of roads. Algorithms as well as time complexity analysis are presented.

Reactive planning is studied for multiple mobile agents. The approach taken is distributed, i.e., each planning agent independently plans its own action based on its map information. An environment contains mobile agents of different capacities with respect to knowledge about the environment, planning algorithms, etc. A model for such reactive agents is described, and simulation results are presented to show their behavior patterns.>

Motion planning is studied in a time-varying environment. Each obstacle is a convex polygon that moves in a fixed direction at a constant speed. The robot is a convex polygon that is subject to a speed bound. A method of determining whether or not there is a translational collision-free motion for a polygonal robot from an initial position to a final position and of planning such a motion, if it exists, is presented. The method makes use of the concept of configuration spaces and accessibility. An algorithm is given for motion planning in such an environment, and its time complexity is analyzed.>

Motion planning for a point robot is studied in a two-dimensional time-varying environment. The obstacle is a convex polygon that moves in a fixed direction at a constant speed. The point to be reached (referred to as the destination point) also moves along a known path. The concept of accessibility from a point to a moving object is introduced, and it is used to define a graph on a set of moving obstacles. The graph is shown to exhibit an important property, that is, if the moving point is able to move faster than any of the obstacles, a time-minimal path is given as a sequence of edges in the graph. An algorithm is described for generating a time-minimal path, and its execution time is analyzed.>

A method is presented for planning a path in the presence of moving obstacles. Given a set of polygonal moving obstacles, the authors focus on generating a path for a mobile robot that navigates in the two-dimensional plane. Their methodology is to include time as one of the dimensions of the model world. This enables the authors to regard the moving obstacles as being stationary in the extended world. For a solution to be feasible, the robot must not collide with any other moving obstacles, and, also, it must navigate without exceeding the predetermined range of velocity, acceleration, and centrifugal force. The authors investigate an appropriate model to represent the extend world for the path-planning task, and give a time-optimal solution using this model.>

A study is performed of the problem of planning a collision-free path for a robot in a time-varying environment. It is assumed that an obstacle moves along a known path. The formulation also allows the destination point (the point to be reached) to move along a predetermined path. A concept of 'accessibility' from a point to a moving object is introduced and is used to determine a collision-free path. An environment which contains some uncertainty in which the robot needs to see and possibly plan an alternative path is also considered. The ability to deal with moving obstacles is useful in a variety of visual tasks such as the navigation of an autonomous vehicle and the interaction between robot arms.>

A method is presented for planning a path in the presence of moving obstacles. Given a set of polygonal moving obstacles, a path is generated for a mobile robot that navigates in the two-dimensional plane. Time is included as one of the dimensions of the model world. This allows the moving obstacles to be regarded as stationary in the extended world. For a solution to be feasible, the robot must not collide with any other moving obstacles and must navigate within the predetermined range of velocity, acceleration, and centrifugal force. A spatial index is used to facilitate geometric search for the path-planning task. Computer simulation results are presented to illustrate the feasibility of this approach.>