Pathfinding for mobile sensor networks on the fly

As computing power continues to increase and embedded electronic applications go beyond what was once thought possible, cyber-physical systems (CPSs) are becoming a significant area of interest. A CPS comprises a closely interacting network of physical and computational components that responds rapidly and automatically to physical inputs with physical outputs. One category of CPSs is mobile sensor networks (MSNs). Through the action of the physical components of the system, these networks can autonomously investigate and report on their environment. MSNs have a variety of potential applications. For example, a ground-based MSN can be used to identify hazardous contaminants,¹ and a ground and air MSN can be used to localize targets.² A network of satellites has also been used to monitor air quality.³

Efficient management of MSNs relies on computing local instructions in real time for each physical component, or agent, of the MSN to enable it to freely navigate its environment. This is a challenging task that must consider nonlinear dynamics, various constraints, and changing environments.⁴ We have developed a method—virtual motion camouflage (VMC)—for rapidly generating optimal agent trajectories, inspired by the motion camouflage phenomenon observed in mating hoverflies,^{5, 6} and have assessed its performance in controlling an MSN using a robot testbed.

VMC is a varying subspace method. The subspace is constructed by a constant but optimizable reference point and a virtual prey motion that is represented by B-spline curves. Within the subspace, the actual trajectory of an agent (i.e., translational motion) is controlled by a single-degree-of-freedom vector (the so-called path control parameter). In the achieved nonlinear programming problem, both the subspace and the path control parameters are optimized simultaneously. Also, to more effectively find obstacle-free trajectories, the VMC method can be augmented with fast path planning algorithms, such as the wavefront approach.⁷

Although we have evaluated the new method in space-, air-, and ground-based simulations,^{5, 6,8} it makes more sense to have an intermediate testbed before directly applying it to a high-cost, high-risk real system. Such a testbed can be controlled so that different aspects of the new algorithm can be tested with minimal losses or costs in the event of a failure. Recently, we developed a low-cost robot testbed at the Air Force Research Laboratory's (AFRL) Space Vehicles Directorate (see Figure 1). This testbed is built around a modular robot platform, in which the robots can carry different sensors and the robot dynamics can be heterogeneous. The robots exchange data with laptops using Bluetooth communication. The number of robot agents that can be connected is limited by the communication hardware (currently, this limit is seven). In the current design, an overhead webcam provides data about the environment, such as the obstacle and robot locations, to the robots using a template matching technique.⁹Images captured from the webcam are processed at a rate of 7Hz using a prediction strategy for the localization of robots and searching the entire frame for new obstacles.

Figure 1. Low-cost, vision-based robot testbed for developing and verifying trajectory-planning and other algorithms to support cyber-physical systems.

Using this testbed, we have demonstrated that the VMC algorithm is capable of rapidly computing the optimal trajectories of multiple robots operating in varying dense obstacle environments. Starting with a single robot agent, and increasing to three, the algorithm was applied to a number of scenarios, including the following: randomly distributed, dense obstacle environments; clustered, dense obstacle environments; and close-quarters environments, all with different initial and final conditions. The algorithm is considered to have performed successfully if a trajectory for each agent is achieved within a few seconds. Typical tests for the algorithm can be seen in Figure 2. Optimal trajectories for all the examples shown here were successfully computed within the time constraints. However, it is worth noting that the experimental settings and the parameters of the VMC method may have to be tuned for different applications.

Figure 2. Left: Typical testbed run with three robots in a randomly distributed, dense obstacle environment. Middle: Typical testbed run with two robots in a clustered and dense obstacle environment. Right: Typical testbed run with two robots in close quarters.

A graphical user interface for the testbed allows users to change the trajectory planning method and the parameters used (see Figure 3). Also, robot connections can be managed, on-board sensors can be viewed, and desired robot localization can be modified.

Figure 3. Graphical user interface designed for the testbed.

In addition to the optimal trajectory planning algorithm for MSNs, the testbed could also be used in many other applications. With proper enhancements in communication and software, the testbed can test scalable and decentralized planning algorithms and study the communication architecture for MSNs. With rigorous analysis and hardware validation, the new algorithm could be used in many MSN applications, such as formation flying, border security, and wind farms. In the near future, the testbed will be further enhanced in a joint effort between the University of Central Florida and AFRL and used to test new algorithms for mobile sensor networks.