IntroductionObstacle AvoidanceObstacle MappingPath FindingPath FollowingResultsDiscussionObstacle Avoidance with Lane FollowingResultsDiscussionThomas Coffee ∘ Michael Fleder ∘ Collin Johnson 17 Oct 2006Obstacle Avoidance for a Lane-Following Vehicle6.897 Robotics Science & Systems II: Laboratory #2IntroductionThis report describes the development of an obstacle-avoiding path controller for a car-like vehicle following (possibly obstructed) lanes on flat ground. The intended vehicle has independent control of acceleration/braking below a fixed maximum speed and two-wheel steering within a fixed turn radius, where the turn radius is significant compared to the distances traversed. A forward-mounted LIDAR unit provides high-resolution distance measurements to line-of-sight obstacles in front of the vehicle; the rear is blind. The vehicle utilizes dead-reckoning capabilities developed in Lab #1 for state estimation.The controller receives a dynamically updated sequence of waypoints from another software module designed to follow visual lane markings on the ground. It attempts to reach these waypoints in order, following a smooth path while avoiding collisions with (possibly moving) obstacles in its environment; if a waypoint is found to be unreachable without collisions, the controller moves on to the next waypoint in the sequence, though the lane follower is normally expected to reacquire the road and update the waypoint sequence to prevent this situation.The controller and supporting software developed herein were designed for and tested on a small indoor rover, as an exercise supporting development of autonomous driving software for automobiles. The indoor rover uses a two-wheel differential drive system with a software layer imitating the driving dynamics of a standard car. However, with differential drive and a low maximum speed, it can effectively change speed and steering instantaneously within its driving limits, without risk of instability. Thus these dynamics can be neglected when dealing with the indoor rover, whereas they must be considered in realistic automobile driving scenarios.The algorithms described here are not intended to provide optimal solutions to even restricted variants of the problems considered. Rather, they constitute the simplest (and easiest-to-implement) approaches found to yield certain desirable characteristics in practical application. Hence, the results presented here will focus on subjective assessments of performance in example exercises rather than theoretical justification of the algorithms.Obstacle AvoidanceThe diagram below shows the controller software architecture. Box labels refer to software modules by name, while arrow labels refer to the data structures published between modules over the lightweight communications (LC) system. The lane follower (here an abstract module) publishes waypoint lists used by the controller. There is currently no mechanism for feedback to the lane follower (waypoint status messages), since the existing lane follower has no mechanism for utilizing this information. A more mature system would almost certainly close this loop.Thomas Coffee ∘ Michael Fleder ∘ Collin Johnson 17 Oct 2006Our team split the obstacle avoidance software into three modules linked over LC: occupancy_grid, PathFinder, and path_controller. This setup facilitates interface management in software development and testing, and (more importantly) separates processes with different resource requirements into independent threads, providing mostly automatic tuning of update frequencies. However, the LC system also bounds the size of data structures exchanged between modules, capping the occupancy grid size to 125 × 125 cells in the current implementation. This was adequate for our purposes, but could certainly be improved in future systems through more sophisticated message passing.The occupancy_grid module receives 75Hz scans (laser_t) from the LIDAR: each contains 180 range measurements, spaced at 1° angular intervals over the vehicle's forward field of view, with a ~20-80m horizon. Based on the vehicle's current position/orientation estimate (pose_state_t), the module projects these obstructed points in space onto a square grid fixed to the ground plane, producing a discretized two-dimensional obstacle map of the visible world. It then expands each point on this obstacle map into a disk with the diameter of the vehicle, thus producing a map of forbidden positions in the vehicle's configuration space (occupancy_grid_t). The occupancy_grid module can produce occupancy map updates in sync with the LIDAR at 75Hz on a reasonable PC; however, the current implementation manually downgrades this to 7.5Hz to free up more CPU resources for the PathFinder module. It uses 0.1m resolution on the 125 × 125 grid for a 12.5m × 12.5m map.LIDARORC BoardIMUdead_reckonsplintersplinter_as_carsickxsenslane followeroccupancy_gridPathFinderpath_controllerlaser_timu_todometry_update_tpose_state_tpose_state_toccupancy_grid_twaypoint_list_tshortest_path_tgas_steer_tsplinter_drive_toccupancy_grid_tThomas Coffee ∘ Michael Fleder ∘ Collin Johnson 17 Oct 2006The PathFinder module receives a dynamically updated sequence of waypoints from the lane following software. It plans a path to the first waypoint in the sequence via A* search on the occupancy grid. If no path is found through the occupancy map to the current waypoint, it targets the next waypoint in the sequence and tries again. This module publishes a sequence of grid cells on the unoccupied occupancy grid, constituting a path of minimum “taxicab” distance to the current waypoint (shortest_path_t). This module makes no attempt to account for the dynamic constraints of vehicle motion.The path_controller module receives both the occupancy map from occupancy_grid and the “shortest” path from PathFinder in addition to the vehicle position state estimate. It attempts to construct a “smooth” path consistent with the dynamic constraints of the vehicle while topologically similar to the grid cell path given by PathFinder. It first searches along the grid path from PathFinder until it finds a cell obscured by an obstacle in the current view of the vehicle, then heads toward the immediately preceding cell. It replans when it reaches this intermediate waypoint or if it encounters an osbtacle en route. The controller otherwise ignores path plan updates en route to its intermediate waypoint to avoid