High-speed autonomous robot navigation in dynamic
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.
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.
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,
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,
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.
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,
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
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.
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
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
Motion planning in
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
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
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,
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.
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.
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,
Z. Online Suboptimal Obstacle Avoidance, The International Journal of
Robotics Research, 2000, vol. 19, 5: pp. 480-497.
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.
Ben Ezair, Tamir Tassa, Zvi 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
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.
of road vehicles
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.
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.
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
Z, Lu H. Computation of Path Constrained Time Optimal Motions With Dynamic
Singularities. ASME. J. Dyn. Sys., Meas., Control. 1992;114(1):34-40.
Tarkiainen and Z. Shiller, "Time optimal
motions of manipulators with actuator dynamics," 
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.
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,
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
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
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.
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
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.