Simultaneous Cooperative Exploration and Networking

Curve Tracking Control for Autonomous Vehicles with Rigidly Mounted Range Sensors

Curve tracking control is fundamental for autonomous vehicles following desired paths, e.g. staying in lanes, or avoiding obstacles. An example in which this becomes relevant is when an autonomous vehicle is to follow the curb or the lane markings. Below figure shows the autonomous vehicle Sting-I that represented Georgia Tech in the DARPA Urban Grand Challenge in 2007. We designed a curve tracking control law in order to be used as a lane following component in the Georgia Tech Urban Grand Challenge system. It should be noted that our results may be applied to other types of autonomous vehicles with rigidly mounted range sensors. We briefly introduce our hybrid strategy of switching between control laws when the vehicle gets close to singularities. Define the safety zone such that once the vehicle enters the safety zone, then the vehicle will never leave and the curve tracking behavior is stabilized without collision. Now, the controller design problem is reconsidered so that the goal of the controller is to steer into the safety zone. Switching controllers, which steer the system into the safety zone in finite time, are depicted in the following figure. Rigorous proof and extensive simulation results verify the validity of the proposed switching control laws. 3D Simulations results are provided to demonstrate the effectiveness of switching control laws (see cylinder3.mpeg attached below). In the following figure, MATLAB simulation result is depicted. This figure shows a vehicle circling a lane-shaped curve in the clockwise direction starting from multiple initial positions. We vary the vehicle's initial x-coordinate from -8 to 8, and y-coordinate from -6 to 6 with initial orientation 135 degree measured counterclockwise from the x-axis.

Battery Level Estimation of Mobile Agents Under Communication Constraints

Consider a team of mobile agents monitoring large areas, e.g. in the ocean or the atmosphere, with limited sensing resources. Only the leader transmits information to other agents, and the leader has a role to monitor battery levels of all other agents. Every now and then, the leader commands all other agents to move toward or away from the leader with speeds proportional to their battery levels. The leader then simultaneously estimates the battery levels of all other agents from measurements of the relative distances between the leader and other agents. We propose a nonlinear system model that integrates a particle motion model and a dynamic battery model that has demonstrated high accuracy in battery capacity prediction. The extended Kalman filter (EKF) is applied to this nonlinear model to estimate the battery level of each agent. We improve the EKF so that, in addition to gain optimization embedded in the EKF, the motions of agents are controlled to minimize estimation error. MATLAB simulation results are presented to demonstrate effectiveness of the proposed method. First figure shows the EKF by fixing the speed of an agent. Estimated battery level is shown in red, and true battery level is shown in blue. Initially, the difference between estimated battery level and true battery level is 1.5. However, after running the EKF within 17 time steps, estimated battery level converges to true battery level. Second figure shows the EKF by adjusting the speed of an agent periodically. At every 5 steps under the EKF, the speed of each agent is adjusted to minimize the error covariance predicted 5 steps forward in time. Initially, the difference between estimated battery level and true battery level is 1.5. However, after running the EKF within 6 time steps, estimated battery level converges to true battery level. Observe that, using adaptive speed gain, estimated battery level converges to true battery level faster than the case where fixed gain is used. In other words, time efficiency of the EKF increases using adaptive speed gain.

A provably complete exploration strategy by constructing Voronoi Diagrams

We address the problem of exploring an unknown workspace using a vehicle equipped with range sensors. Such sensors have the ability to determine a point on an obstacle boundary that is closest to the vehicle. We call such a point the closest point. If obstacle boundaries appear on both sides of the vehicle, then a closest point can be determined on each boundary. A path that is at an equal distance from these closest points is a Voronoi edge. All such Voronoi edges form the Voronoi diagram that reveals the topological structure of the workspace. If the vehicle visits all Voronoi edges in the workspace, then we consider the workspace as being completely explored. We present novel exploration algorithms, called Boundary Expansion algorithms, that enable the construction of Voronoi diagrams over unknown areas using a vehicle equipped with range sensors. The underlying control law uses range measurements to make the vehicle track Voronoi edges between two obstacles. This Voronoi edge tracking control law guarantees that the trajectory of the vehicle is smooth. The exploration algorithms make decisions at vertices in the Voronoi diagram to incrementally expand the already visited parts of the environment until a complete Voronoi diagram is constructed in finite time. Our exploration algorithms are provably complete, and the convergence of the control law is guaranteed. Simulations (see center_follow1.avi attached below) and experimental results (see success.avi attached below) are provided to demonstrate the effectiveness of both the control law and the exploration algorithms. The following figure shows successful experimental results of both the control law and the exploration algorithms. A robot is equipped with IR sensors to detect an obstacle environment. As the robot maneuvers in the workspace, a MATLAB plot is displayed in real time to show the detected obstacle environment. The real-time MATLAB plot is depicted above the corresponding obstacle environment. The robot is depicted as a dotted circle. In addition, the trajectory of the robot is plotted as a blue curve. On the trajectory of the robot, intersections are marked with small circles. In the MATLAB plot, a rounded rectangle is drawn around each intersection with a blocked sector.

Simultaneous Cooperative Exploration and NeTworking (SCENT) based on Voronoi diagrams in 2D environments

We develop strategies that enable multiple intelligent vehicles to cooperatively explore complex and dangerous territories. These strategies are called Simultaneous Cooperative Exploration and Networking (SCENT) algorithms. The workspace is considered completely explored if Voronoi diagrams are fully constructed. The vehicles are initially deployed at arbitrary locations and are not necessarily aware of the existence of other vehicles. Each vehicle starts with Boundary Expansion algorithms to explore its surroundings while deploying communication devices. Every vehicle drops communication devices and expands an information network while constructing a topological map based on the Voronoi diagram. As the information network weaved by each vehicle grows, intersections eventually happen so that the topological maps are shared. This allows for distributed vehicles to share information with other vehicles that have also dropped communication devices. A performance analysis of SCENT algorithms shows that in a bounded workspace, the time spent to complete the exploration decreases as the number of vehicles increases. We provide analytical formulas for this relationship. We verify the efficieny of SCENT algorithms through both MATLAB simulations (see center_follow2.avi attached below) and experiments using two mobile robots (see below for the link to SCENT experiments). First figure shows MATLAB simulations for one vehicle constructing Voronoi diagrams in a rectangular shaped workspace using Boundary Expansion algorithms. The inintial position of the vehicle is (2,20). The obstacle boundary is shown as red curve. The trajectory of a vehicle is plotted with blue points. Along the vehicle's trajectory, the intersections are marked with large green dots. The exploration time is 99.05 time units. Second figure shows MATLAB simulations for two vehicles constructing Voronoi diagrams in a rectangular shaped workspace using SCENT algorithms. The initial positions of two vehicle are (2,20) and (45,2) respectively. The trajectories of two vehicles are marked with blue points and black circles respectively. The exploration time using two vehicles is 29.67 time unit which is less than one third of exploration time using one vehicle.

Capturing Multiple Intruders in a Graph Using the Information Network

As a result of SCENT algorithms, the information network is created concurrently with the topological map based on Voronoi diagrams in the workspace. The resulting information network and the topological map are used to solve complex and coordinated multi-robot tasks. We introduce an application of the constructed network to the problem of capturing multiple intruders in the workspace. We provide an algorithm to capture all intruders in an arbitrary connected graph. Based on this algorithm, we prove that the minimum number of searchers to capture all intruders in Voronoi diagrams (topological map of the workspace) is less than the number of obstacles in the workspace. Intruder capturing algorithm is implemented using an interactive simulation. In this simulation, an user generates an arbitrary connected graph and chooses initial positions of intruders in the graph. Then, using our algorithm, searchers are automatically deployed to capture all intruders.

Simultaneous Cooperative Exploration and NeTworking (SCENT) based on Voronoi diagrams in 2.5D environments

We extend SCENT algorithms from ground vehicles to aerial vehicles. In computer graphics and video game development, a 3D scene is often created using a 2.5D strategy in the sense that the movements of video game agents are confined within 2D planes. This strategy greatly reduces the possible outcomes associated with agent movements and the amount of computation needed to render real-time 3D visualization. As such, we introduce 2.5D SCENT algorithms so that multiple vehicles can explore 2.5D workspace in a time efficient way. A 2.5D workspace is composed of several 2D planes with different elevations. At each elevation, 2D SCENT algorithms can be applied, since 2D Voronoi diagrams are well defined. One major modification in 2.5D SCENT algorithms is that the information network has 3D structure, since a communication link exists between two nodes at different elevation. We further provide an analytical formula for the relationship between the number of vehicles and the time spent to complete the exploration and show that 2.5D SCENT algorithms lead to time efficient construction of Voronoi diagrams in an unknown 2.5D workspace. The following figure shows the illustration of 2.5D workspace. There are three sub-workspaces (2D planes) in this workspace. The rectangles with distinct color illustrate distinct obstacles in an 3D environment. Black dots in each sub-workspace illustrate positions of communication devices deployed at intersections on each plane. (see summary)


Figure 1.


Figure 2.

Figure 3.

Figure 4.

Figure 5.

Figure 6.

Figure 7.

Figure 8.

Figure 9.