Chapter 1
Introduction

1.1 Historical perspective of mobile robotics

Since its first application in the 1940s, robot arms or manipulators have demonstrated a great success in the world of industrial manufacturing. These robot arms can perform repetitive tasks such as spot welding, painting, machine loading and unloading, electronic assembly, packaging, and palletizing, among other activities. However, industrial robots lack of one fundamental property: mobility. The fixed-base manipulator has a limited range of motion that depends on where it is bolted down. The ability to move is what makes a mobile robot travel freely throughout a given environment. However, this mobility advantage can also be its doom if the robot does not account for a reliable navigation strategy.

One navigation approach is to just react to what is sensed; this is called reactive navigation [7, 186, 193]. For example, the robotic tortoise Elsie, built in the 1940s by the Edison-Swan Electric Company, reacted to her environment and could seek out a light source without having any explicit plan or knowledge of the position for the light, see Figure 1.1a. This reactive navigation strategy is exploited today by Automated Guided Vehicles (AGVs) in many factories [6, 144]. For example, Amazon uses AGVs in more than ten of its warehouses located in the US. These robots were developed by the company Kiva, later acquired by Amazon in 2012 and becoming AmazonRobotics (https://www.amazonrobotics.com).

Reactive systems can be fast and simple when sensing is connected directly to action, that is, there is no need for resources to hold and maintain a representation of the world nor any capability to reason about that representation [41]. However, such reactive navigation requires a fixed infrastructure where the robot is going to move, for example, a painted line on the floor, a buried cable that emits radio-frequency signals, or wall-mounted bar codes. The second major drawback of this approach is that it limits the mobility of the robot to those areas where the guidance system is located or installed; this explains why AGV are usually applied in factories.

Figure 1.1 Mobile robots and reactive navigation. Example of mobile robots based on reactive navigation strategies.

With the explosion of digital technology in the 1970s, a group of engineers working at the Stanford Research Institute (SRI) developed the first mobile robot to be operated using autonomous reasoning [159]. The robot Shakey was capable of 3D perception and created a map of its environment and then reasoned about the map to plan a path to its destination, see Figure 1.2a. An optical rangefinder and a vidicon television camera with controllable focus and iris were mounted on a tilt platform for sensing. Offboard communication was provided via two radio channels: one for video and the other providing command and control. This ability to make maps and reason about them made Shakey capable of performing more complex tasks than former robots based on reactive navigation strategies. After Shakey, the next big step in the field of mobile robotics came from the Robotics Institute at Carnegie Mellon University in the 1980s [28]. The Terregator robot (Terrestrial Navigator) was designed to operate autonomously in outdoor scenarios, see Figure 1.2b. It was a six-wheeled skid-steer robot utilizing compliant tires for suspension. Terregator subsystems included locomotion, power, computation, controls, wireless telemetry (serial links and two channels of UHF video), orientation sensors, and navigation payloads. The robot's onboard control system consisted of a central processing unit (CPU) linked to motor controllers. This CPU calculated the robot's position and orientation from a gyroscope, wheel encoders, and inclinometers (dead-reckoning). Additionally, this system was also responsible for guiding the robot to a commanded destination provided by an offboard supervisor (remote command station). This supervisor made use of the images coming from the video camera mounted on the vehicle. Terregator was even used for mapping a portion of a mine thanks to its path planning and mapping capabilities [28]. Another big milestone in the early ages of mobile robotics came from the University of Munich in Germany. Several vehicles developed by Prof. Ernst Dickmanns, e.g. Daimler-Benz VITA-2 and UniBwM VaMP, drove autonomously on European highways at speeds up to 130 km/h, see Figure 1.2c. This astonishing leap was achieved by using a visual feedback control system that tracked the road boundaries. This advanced control system ran in a multiprocessor image processing system using contour correlation and curvature models together with the laws of perspective projection [52]. The vehicle's position was estimated relative to the driving lane and road curvature by means of a Kalman filter. In 1994, the VaMP driverless car designed by Prof. Dickmanns drove 1600 kilometers, of which 95% were driven autonomously [51].

Figure 1.2 Autonomous mobile robots. Example of pioneering autonomous mobile robots.

These pioneering mobile robots opened the door to the significant achievements in the field of mobile robotics during the last twenty years. Today, mobile robots have explored other worlds such as Mars or the Moon, e.g. MER rovers and MSL rover [87, 194; mobile robots have worked at Antarctica seeking meteorites, e.g. Nomad robot [5; robots are able to clean our houses, e.g. iRobot Roomba; to perform harvesting activities in agriculture, e.g. ASI autonomous tractor; and they are also present in our schools, like the SoftBank Robotics NAO humanoid robot.

1.2 Path planning. Definition and historical background

A fundamental task for any mobile robot is its ability to plan collision-free trajectories from a start to a goal position or visiting a series of positions, i.e. regions of interest, among a collection of (static) obstacles. This is the robot's cognitive level. Cognition generally represents the purposeful decision-making and execution that a system utilizes to achieve its highest-order goals. Given a map and a goal position (or a list of high-level goals), path planning involves identifying a trajectory that will cause the robot to reach the goal position (a 2D point) or pose (a 2D point and an orientation) when executed [35, 135, 191]. It bears mentioning that position refers to the longitudinal and lateral coordinates in a Cartesian frame. Pose also considers the orientation.

Path planning comprises the highest level within a typical navigation architecture of a mobile robot. As observed in Figure 1.3, there are four big modules or layers. The second layer in this navigation architecture includes the motion controller (or trajectory following strategy), which is responsible for generating the control actions in such a way that the robot follows as accurately as possible the reference trajectory provided by the path planning layer. These control actions will be determined according to the error between the current robot's position and the next desired waypoint. The third layer deals with the low-level PID controllers that ensure that the control actions generated by the motion controller are reached by the robot actuators, i.e. wheel motors. As explained before, it is crucial for the motion controller to know the current position of the robot; this is calculated by the last layer in the robot's navigation architecture: the localization layer. Here, a set of sensors are employed to get the robot's position as accurately as possible. Another significant observation about this traditional navigation architecture is that the execution time or the sampling time of each layer is different. For example, the time to get a response from the path planning layer is on the order of minutes or seconds, the time for the motion control layer is on the order of seconds or hundreds of milliseconds, and the fastest layer comprises the low-level controllers that run on the order of milliseconds.

Figure 1.3 Navigation architecture of a mobile robot. Example of a navigation architecture of a mobile robot (University of Almeria's Fitorobot robot) [78].

The history of robot path planning began with the early computer-controlled robots, i.e. SRI Shakey robot. One of the pioneering references in this field is the book "Robot Motion Planning" authored by Jean-Claude Latombe in 1980 [132],1. At that time, the most advanced planners were barely able to compute collision-free paths for objects moving in planar workspaces. In the 1990s, researchers working in this field faced another challenge: planning motions in the presence of kinematic constraints like non-holonomic robot systems2, e.g. a car that cannot rotate around its axis without also changing its position [133]. At the beginning of the twenty-first century, robot planners could be applied to robots with many degrees of freedom in complex environments, coordinate multiple robots, and handling dynamic environments. In 2005 and 2006 other key references appeared in the field of mobile robotics: "Principles of Robot Motion: Theory, Algorithms, and Implementations" by Choset et al. [35] and "Planning Algorithms" by Stephen LaValle [135]. These books...