Paslin Laboratory for Robotics and Autonomous Vehicles

HOME

 

 

High-speed autonomous robot navigation in dynamic urban environments

This research seeks to develop and experimentally validate safe high-speed navigation of autonomous robot vehicles in urban environments. It is motivated by the anticipated use of autonomous vehicles in everyday urban environments, populated by static obstacles as well as moving pedestrians and other vehicles. It is also motivated by a need for robotic first responders that will assist search and rescue teams in urban environments and industrial sites such as nuclear reactors.

Video clip

 

Off-road motion planning

This research is aimed at developing novel motion planning and navigation algorithms to guide autonomous vehicles in unstructured outdoor environments, such as during surface exploration of remote planets and terrestrial search and rescue missions. The planner is based on an original physics-based motion planner that takes into account surface topography, soil properties, and vehicle dynamics.

Video clip

Video clip  

Z. Shiller and Y. R. Gwo, "Dynamic motion planning of autonomous vehicles," in IEEE Transactions on Robotics and Automation, vol. 7, no. 2, pp. 241-249, Apr 1991.

Z. Shiller and M. P. Mann, "Dynamic stability of off-road vehicles," 2004 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) (IEEE Cat. No.04CH37566), 2004, pp. 1849-1853 vol.2.

M. P. Mann and Z. Shiller, "Dynamic Stability of a Rocker Bogie Vehicle: Longitudinal Motion," Proceedings of the 2005 IEEE International Conference on Robotics and Automation, 2005, pp. 861-866.

M. P. Mann and Z. Shiller, "Dynamic stability of off-road vehicles: a geometric approach," Proceedings 2006 IEEE International Conference on Robotics and Automation, 2006. ICRA 2006., Orlando, FL, 2006, pp. 3705-3710.

Z. Shiller, M. P. Mann and D. Rubinstein, "Dynamic Stability of Off-Road Vehicles Considering a Longitudinal Terramechanics Model," Proceedings 2007 IEEE International Conference on Robotics and Automation, Roma, 2007, pp. 1170-1175.

M. Mann and Z. Shiller, "Dynamic stability of off-road vehicles: Quasi-3D analysis," 2008 IEEE International Conference on Robotics and Automation, Pasadena, CA, 2008, pp. 2301-2306.

K. Iagnemma, Shingo Shimoda and Z. Shiller, "Near-optimal navigation of high speed mobile robots on uneven terrain," 2008 IEEE/RSJ International Conference on Intelligent Robots and Systems, Nice, 2008, pp. 4098-4103.

Time optimal control of all-wheel drive vehicles

Future autonomous vehicles are expected to be driven by actuated wheels.  The individual control of each wheel allows better control of the vehicle’s dynamic stability at high speeds and better overall performance.  However, the distribution of the control inputs between the wheels is complicated by the indeterminate nature of the vehicle dynamics (more control inputs than degrees of freedom).  This inherent indeterminisity is resolved by adding a virtual suspension model, which allows to explicitly compute the individual wheel torques.  The all-wheel drive model produces a larger set of admissible speeds and accelerations, and hence results in faster speeds and shorter motion times than the current front or rear-while drive vehicles. 

A. Stern and Z. Shiller, "Control allocation of all-wheel drive vehicles: A longitudinal model," 2013 IEEE/RSJ International Conference on Intelligent Robots and Systems, Tokyo, 2013, pp. 2862-2867.

3dmap

Traversability and homotopy classes of optimal trajectories on rough terrain 

This research concerns the development of efficient algorithms to generate a set of local optimal paths between two given end points in cluttered environments or over open terrain. The local optimal paths are selected from the set of shortest constrained paths through every node (one for each path) in the graph, generated by running twice a ”single-source” search. The initial set of the shortest constrained paths spans the entire search space and includes local optimal paths with costs equal or better than the longest constrained path in the set. The search for the optimal path is transformed to a search for the best path in each homotopy class generated by this search. The initial search is of complexity O(nlogn), and the pruning procedure is O(nmlogm), where n is the number of nodes and m is the number of homotopy classes generated by this search. The algorithm is very efficient and applicable to computing the global optimal trajectories for autonomous vehicles over rough terrain.  

Y. Fujita, Y. Nakamura and Z. Shiller, "Dual Dijkstra Search for paths with different topologies," 2003 IEEE International Conference on Robotics and Automation (Cat. No.03CH37422), 2003, pp. 3359-3364 vol.3.

3d

Motion planning in dynamic environments

The velocity obstacle is an effective tool for planning collision-free maneuvers in dynamic environments.  It maps the moving obstacle to the configuration space of the moving robot that allows to select a single avoidance maneuver (if one exists) that avoids any number of obstacles that move on any known trajectories.  It is used to generate avoidance maneuvers of a single vehicle and of a group of robots. 

Safety can be ensured using an adaptive time horizon, which is used to truncate the velocity obstacle so that the boundary of the velocity obstacle closely approximates the boundary of the set of inevitable collision states. The clear partitioning between safe and unsafe velocities allows safe planning with only one step look ahead, and can produce near optimal trajectories, compared to the conservative trajectories produced when using an infinite time horizon. This algorithm was used.    

A new on-line planner for dynamic environments was developed that is based on the concept of Velocity Obstacles (VO). It addresses the issue of motion safety, i.e. avoiding states of inevitable collision, by selecting a proper time horizon for the velocity obstacle. The proper choice of the time horizon ensures that the boundary of the velocity obstacle coincides with the boundary of the set of inevitable collision states.  This time horizon is determined by the minimum time it would take the robot to avoid collision.  The planner generates a near-time optimal trajectory to the goal by selecting at each time step the velocity that minimizes the time-to-go and is out of the velocity obstacle.    The planner takes into account the shape, velocity, and path curvature of the obstacle's trajectory.  It is demonstrated for on-line motion planning in very crowded static and dynamic environments and for on-line coordination of multiple aircraft in a crowded airspace.

Video clip1

Video clip2

Paolo Fiorini Zvi Shiller, Motion Planning in Dynamic Environments Using Velocity Obstacles, The International Journal of Robotics Research, 1998, vol. 17, 7: pp. 760-772. 

P. Fiorini and Z. Shiller, "Time optimal trajectory planning in dynamic environments," Proceedings of IEEE International Conference on Robotics and Automation, Minneapolis, MN, 1996, pp. 1553-1558 vol.2.

Z. Shiller, F. Large and S. Sekhavat, "Motion planning in dynamic environments: obstacles moving along arbitrary trajectories," Proceedings 2001 ICRA. IEEE International Conference on Robotics and Automation (Cat. No.01CH37164), 2001, pp. 3716-3721 vol.4.

O. Gal, Z. Shiller and E. Rimon, "Efficient and safe on-line motion planning in dynamic environments," 2009 IEEE International Conference on Robotics and Automation, Kobe, 2009, pp. 88-93.

Z. Shiller, O. Gal and A. Raz, "Adaptive time horizon for on-line avoidance in dynamic environments," 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems, San Francisco, CA, 2011, pp. 3539-3544. 

Online obstacle avoidance

An efficient online algorithm was developed to near-optimally avoid static obstacles.  It accounts for robot dynamics and actuator constraints.  The robot trajectory (path and speed) is generated incrementally by avoiding obstacles optimally one at a time, thus reducing the original problem from one that avoids m obstacles to m simpler problems that avoid one obstacle each. The algorithm is fast and successfully competes with alternative approaches.  Computation times for the kinematic version of this planner (minimizing distance) averaged 0.5ms for a complete path among 70 tightly spaced obstacles.  This algorithm is applicable for home and outdoor security and fast response applications.

Shiller Z, Gwo Y. Collision-Free Path Planning of Articulated Manipulators. ASME. J. Mech. Des. 1993;115(4):901-908.

S. Sundar and Z. Shiller, "Optimal obstacle avoidance based on the Hamilton-Jacobi-Bellman equation," in IEEE Transactions on Robotics and Automation, vol. 13, no. 2, pp. 305-310, Apr 1997.

Shiller, Z. Online Suboptimal Obstacle Avoidance, The International Journal of Robotics Research, 2000, vol. 19, 5: pp. 480-497.  

Z. Shiller and S. Sharma, "High speed on-line motion planning in cluttered environments," 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, Vilamoura, 2012, pp. 596-601.

Zvi Shiller, Sanjeev Sharma, Ishai Stern and Asher Stern, Online obstacle avoidance at high speeds, The International Journal of Robotics Research, 2013, vol. 32, 9-10: pp. 1030-1047.

Ben EzairTamir TassaZvi Shiller, Planning high order trajectories with general initial and final conditions and asymmetric bounds, The International Journal of Robotics Research, 2014, vol. 33, 6: pp. 898-916.

Motion planning of tracked vehicles

The motions of planar tracked vehicles are governed by three force and moment equations, but driven by only two independent control variables. The force equation perpendicular to the tracks represents a dynamic nonholonomic constraint which is explicitly dependent on vehicle speed. It couples path planning with trajectory planning, that is, solving for vehicle kinematic motions requires specifying vehicle speeds. In contrast, wheeled vehicles are governed by kinematic nonholonomic constraints, allowing separate planning of the path and the trajectory. The nominal track forces required to follow a specified path at desired speeds are computed by first computing vehicle orientations along the path that are consistent with the nonholonomic constraint. The computation of vehicle orientations is formulated as a parameter optimization that minimizes the violation of the equality constraint. The method is demonstrated for planar motions along a circular path on flat and inclined planes.

Shiller Z, Serate W. Trajectory Planning of Tracked Vehicles. ASME. J. Dyn. Sys., Meas., Control. 1995;117(4):619-624.

Emergency maneuvers of road vehicles

Emergency lane-change maneuvers, defined as the sharpest dynamically feasible maneuvers, are computed by minimizing the longitudinal distance of a lane transition, assuming given initial and free final speeds.  The optimal maneuvers are used to determine the minimum  distance beyond which an obstacle cannot be avoided. Plotting the minimum distance in the phase plane provides a valuable design tool for planning safe avoidance maneuvers.    

Shiller Z, Sundar S. Emergency Lane-Change Maneuvers of Autonomous Vehicles. ASME. J. Dyn. Sys., Meas., Control. 1998;120(1):37-44.  

Time optimal trajectory planning

One of the basic problems in robotics is that of motion planning, which attempts to move a robot from a given initial state to a destination state, while avoiding collisions with known static and moving obstacles.  We distinguish between a path and a trajectory: a path represents a sequence of positions, whereas a trajectory can be viewed as a path and a velocity profile, defined in the higher dimensional state space, where every point defines a position and velocity at that point. 

Early work on trajectory planning was based on optimal control theory, such as Pontryagin's maximum principle, which formulates the time optimization problem as a two-point boundary value problem, which is solved by searching for the optimal control required to generate the optimal trajectory.  

An efficient approach that facilitates a practical realization of time-optimal motion planning decouples the problem by representing robot motions by a path and a velocity profile along the path.  This reduces the trajectory planning problem to two smaller problems: a) computing the optimal velocity profile along a given path, and b) searching for the optimal path in the n-dimensional configuration space.  We have proposed several efficient algorithms for computing the time optimal velocity profile and for searching for the global time-optimal trajectory.   

S. Sundar and Z. Shiller, "Near-time optimal path planning using potential functions," Intelligent Robots and Systems '91. 'Intelligence for Mechanical Systems, Proceedings IROS '91. IEEE/RSJ International Workshop on, Osaka, 1991, pp. 1269-1274 vol.3.

Shiller Z, Lu H. Computation of Path Constrained Time Optimal Motions With Dynamic Singularities. ASME. J. Dyn. Sys., Meas., Control. 1992;114(1):34-40.

M. Tarkiainen and Z. Shiller, "Time optimal motions of manipulators with actuator dynamics," [1993] Proceedings IEEE International Conference on Robotics and Automation, Atlanta, GA, 1993, pp. 725-730 vol.2.

Shiller Z, Chang H. Trajectory Preshaping for High-Speed Articulated Systems. ASME. J. Dyn. Sys., Meas., Control. 1995;117(3):304-310. 

Z. Shiller and S. Dubowsky, "Time optimal paths and acceleration lines of robotic manipulators," 26th IEEE Conference on Decision and Control, Los Angeles, California, USA, 1987, pp. 199-204.

Energy optimal trajectory planning

The motions of articulated systems along specified paths are optimized by minimizing a time-energy cost function. The necessary conditions for optimality lead to a compact two point boundary value problem that requires the iterations of only one boundary condition. The optimal control obtained for this problem is smooth, as opposed to the typically discontinuous time optimal control.  The smoother time-energy optimal trajectory is shown to result in smaller tracking errors than the time optimal trajectory.

Shiller Z. Time-Energy Optimal Control of Articulated Systems With Geometric Path Constraints. ASME. J. Dyn. Sys., Meas., Control. 1996;118(1):139-143.

Motion planning of humanoids

This work presents a practical motion planner for humanoids and animated human figures. Modeling human motions as a sum of rigid body and cyclic motions, we identify body postures that represent the rigid-body part of typical motion patterns.  This leads to a model of the configuration space that consists of a multi-layered grid, each layer corresponding to a single posture.  A global search through this reduced configuration space yields a feasible path and the corresponding postures along the path.  A velocity profile is then calculated along the optimal path, subject to the speed and acceleration limits assumed for each posture.  Cyclic motions, generated from primitive cyclic motion patterns for each posture, are then added to the trajectory produced by the path planner. This kinematic motion is then modified to result in dynamically consistent behavior.

Z. Shiller, K. Yamane and Y. Nakamura, "Planning motion patterns of human figures using a multi-layered grid and the dynamics filter," Proceedings 2001 ICRA. IEEE International Conference on Robotics and Automation (Cat. No.01CH37164), 2001, pp. 1-8 vol.1.

High mobility and special purpose mobile robots

A small mobile robot was developed to move at high speeds in cluttered environments. It is instrumented with two laser scanners and an IMU (Inertial Measurement) sensing unit, and a PIC based motion controller.  This robot was demonstrated to move along an obstacle course at high speeds of around 1.5 m/s, yet maintaining high tracking accuracy.  The next generation of this robot has front steering and four hub motors at the wheels.  It consists of a unique truss structure, which makes it light weight and easily to disassemble.      

Video clip

DSCN2443

Humanitarian robotics-- student projects

Assistive robots were developed to assist the elderly in daily tasks.  The systems developed have ranged from helping people to reach high places, climbing stairs, getting up from the bed, transferring a person between beds, turning pages of a book (shown), and performing cleaning tasks around the house. 

Video clip

Z. Shiller, "A Bottom-Up Approach to Teaching Robotics and Mechatronics to Mechanical Engineers," in IEEE Transactions on Education, vol. 56, no. 1, pp. 103-109, Feb. 2013.