Abstract:
A method plans paths of a set of mobile sensors with changeable positions and orientations in an environment. Each sensor includes a processor, an imaging system and a communication system. A desired resolution of coverage of the environment is defined, and an achieved resolution of the coverage is initialized. For each time instant and each sensor, an image of the environment is acquired using the imaging system. The achieved resolution is updated according to the image. The sensor is moved to a next position and orientation based on the achieved resolution and the desired resolution. Then, local information of the sensor is distributed to other sensors using the communication system to optimize a coverage of the environment.

Description:
FIELD OF THE INVENTION 
     The invention relates generally to mobile sensors, and more particularly to distributed path planning for the sensors. 
     BACKGROUND OF THE INVENTION 
     Mobile sensor can be used to acquire images in a coordinated manner. The images can then be used in applications such as surveilance, cartography, and environmental monitoring. One problem in such systems is planning the paths the sensors should follow, a problem known as path planning. 
     In one such system with holonomic robots, where the controllable degrees of freedom are equal to the total degrees of freedom, anisotropic sensors with a bounded footprint are considered, see Hexsel et al., “Distributed Coverage Control for Mobile Anisotropic Sensor Networks,” Tech. Report CMU-RI-TR-13-01, Robotics Institute, Carnegie Mellon University, January 2013. That system models a 2-dimensional (2D) environment as a polygon, possibly containing obstacles. A fixed objective function maximizes a joint probability to detect objects. The objective function uses an a priori fixed density function that represents an importance of each point in the environment. 
     SUMMARY OF THE INVENTION 
     The embodiments of the invention provide a method for planning paths of a set of mobile sensors, that can be, for example, airborne, ground-based, or underwater. Each sensor includes an imaging system for imaging an environment. The imaging system can use optical imaging, synthetic aperture radar (SAR), hyperspectral imaging, physical aperture radar imaging, for example. Images acquired by the sensors can be used in surveillance, cartography and monitoring applications, among others. 
     At any time instant, each sensor moves to a next position and orientation to optimize a resolution of the imaging system is used to select a resolution for optimal coverage of the environment, according to a pre-specified desired resolution at each point in the environment. As used herein, the resolution depends on the size and density of pixels in the images. It should be noted that the coverage can be complete, or partial and images can overlap or not. 
     In a distributed manner, the motion of each sensor and its orientation are optimized by minimizing a cost function that characterizes how well the environment has been imaged, compared to the pre-specified resolution. To perform this optimization, each sensor communicates with neighboring sensors, and exchanges local information. The images acquired by the sensors can be combined into an overall image of the environment to achieve the desired resolution. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a schematic of an example airborne mobile sensor system according to embodiments of the invention; 
         FIG. 2  is a side view of a sensor and environment in sensor coordinates according to embodiments of the invention; 
         FIG. 3  is a table giving variables, description, and exemplar values used by a model according to embodiments of the invention; 
         FIG. 4A  is a schematic of an example environment according to embodiments of the invention; 
         FIG. 4B  is a schematic of an irregular example environment; 
         FIG. 5  is a top view of the sensor footprint in sensor coordinates according to embodiments of the invention; and 
         FIG. 6  is a flow diagram of a method for planning paths of the sensors shown in  FIG. 1  according to embodiments of the invention. 
     
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
       FIG. 1  shows a set of mobile sensors  100  according to embodiments of our invention. The sensors can be airborne, ground-based or underwater, among others. The sensors can, for example, be arranged in indoor or outdoor drones, aircraft, or satellites. Each sensor includes a processor  101 , an imaging system  102 , and a communication system  103 . The imaging system has a known footprint for imaging an environment  400 , which may depend on the orientation of the sensor. The footprint is a projection of the imaging plane, such as a camera image plane or a radar beam pattern, onto the environment. The imaging system can use, among others, optical imaging, synthetic aperture radar (SAR), hyperspectral imaging, physical aperture radar imaging. For this reason, the term “image” is used broadly. 
     The sensors move along paths  102  to image the environment  400 . The communication system includes a tranceiver so that the sensors can communicate with each other over channels  105 . In the preferred embodiment the channels are wireless using, e.g., radio or optical signals. By exchanging information between neighboring sensors, i.e., sensors within communication range, the sensors can perform the path planning in a distrubted manner. However, it should be undertood that the other communication techniques can also be used, for example some or all of the sensors can use digital fine wire tethers. 
     It is an objective to provide an image resolution over the environment that achieves a specified value at each point in the environment. As used herein, the resolution depends on the size and density of pixels in the images. The model uses a subadditive function to model the resolution provided by overlapping footprints  104 . The model also uses an objective function that is time varying. At each time j, the objective function provides a measure of a difference between a desired resolution and a resolution achieved up to a previous time j−1. 
     Sensor Model 
       FIG. 2  is a side view of a sensor and environment in sensor coordinates. A point z in the environment is located on a line bisecting an angle γ v . The table in  FIG. 3  gives the variables  301 , description  302  and exemplar values  303  used by our model. The variables include a height  311  of the sensor, horizontal  312  and vertical  313  angular widths, position  314  of the sensor, and declination  315  and azimuth  317  angles. The angles specify the orientation of the sensors. In the described embodiment, there are two degrees of freedom, however three degrees are not precluded. 
     For conveninece, most of the subsequent computations use the angle ψ  316  to measure the declination, which is related to the actual declination angle Φ using ψ=90°−Φ. The labeled ranges in  FIG. 2  are given by the following:
 
 Z   max   =H  tan(ψ+γ v /2)
 
 Z   min   =H  tan(ψ−γ v /2)
 
 z=H  tan(ψ).  (1)
 
     As shown in  FIG. 4A , an example regular environment is a 100×100 polygonal region Q in the xy plane. An arbitrary point  401  in the environment is labeled q∈Q. In sensor coordinates, the environment is the zy plane, which is a translated and rotated version of the xy plane. A given sensor is located at a height H above the origin of the zy plane and the angle ψ is measured with respect to the z axis. The height H, and the x,y location specify the position of the sensors. The angles Φ and ψ specify the orientation. 
       FIG. 4B  shows an irregular example irregular environment  500 . 
     Each sensor has the declination angle Φ, with ψ=90°−Φ. When the azimuth angle θ=0, the z-axis of the sensor is aligned with the x-axis of a global coordinate system. All variables associated with the i th  sensor have a superscript i for indexing the sensors. 
       FIG. 5  is an example of a top view of the sensor footprint  104  in sensor coordinates specific to an optical sensor. The footprint extends from Z min  to Z max  as shown in  FIG. 2 . The footprint is a polygon defined by the four labeled vertices (1, 2, 3, 4). In sensor coordinates, the footprint vertices (z k , y k ) corresponding to the k th  vertex are 
     
       
         
           
             
               
                 
                   
                     [ 
                     
                       
                         
                           
                             z 
                             1 
                           
                         
                         
                           
                             y 
                             1 
                           
                         
                       
                       
                         
                           
                             z 
                             2 
                           
                         
                         
                           
                             y 
                             2 
                           
                         
                       
                       
                         
                           
                             z 
                             3 
                           
                         
                         
                           
                             y 
                             3 
                           
                         
                       
                       
                         
                           
                             z 
                             4 
                           
                         
                         
                           
                             y 
                             4 
                           
                         
                       
                     
                     ] 
                   
                   = 
                   
                     
                       [ 
                       
                         
                           
                             
                               Z 
                               min 
                             
                           
                           
                             
                               
                                 - 
                                 
                                   Z 
                                   min 
                                 
                               
                               ⁢ 
                               
                                 sin 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     γ 
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     
                                       h 
                                       / 
                                       2 
                                     
                                   
                                   ) 
                                 
                               
                             
                           
                         
                         
                           
                             
                               Z 
                               max 
                             
                           
                           
                             
                               
                                 - 
                                 
                                   Z 
                                   max 
                                 
                               
                               ⁢ 
                               
                                 sin 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     γ 
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     
                                       h 
                                       / 
                                       2 
                                     
                                   
                                   ) 
                                 
                               
                             
                           
                         
                         
                           
                             
                               Z 
                               max 
                             
                           
                           
                             
                               
                                 Z 
                                 max 
                               
                               ⁢ 
                               
                                 sin 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     γ 
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     
                                       h 
                                       / 
                                       2 
                                     
                                   
                                   ) 
                                 
                               
                             
                           
                         
                         
                           
                             
                               Z 
                               min 
                             
                           
                           
                             
                               
                                 Z 
                                 min 
                               
                               ⁢ 
                               
                                 sin 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     γ 
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     
                                       h 
                                       / 
                                       2 
                                     
                                   
                                   ) 
                                 
                               
                             
                           
                         
                       
                       ] 
                     
                     . 
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
     Let S(θ) be the rotation matrix defined below 
     
       
         
           
             
               
                 
                   
                     S 
                     ⁡ 
                     
                       ( 
                       θ 
                       ) 
                     
                   
                   = 
                   
                     
                       [ 
                       
                         
                           
                             
                               cos 
                               ⁡ 
                               
                                 ( 
                                 θ 
                                 ) 
                               
                             
                           
                           
                             
                               - 
                               
                                 sin 
                                 ⁡ 
                                 
                                   ( 
                                   θ 
                                   ) 
                                 
                               
                             
                           
                         
                         
                           
                             
                               sin 
                               ⁡ 
                               
                                 ( 
                                 θ 
                                 ) 
                               
                             
                           
                           
                             
                               cos 
                               ⁡ 
                               
                                 ( 
                                 θ 
                                 ) 
                               
                             
                           
                         
                       
                       ] 
                     
                     . 
                   
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
           
         
       
     
     The global coordinates (x, y) of a point (z, y) in the sensor footprint are obtained by rotating the point by the azumith angle θ, and translating the footprint by the camera location (c x , c y ): 
     
       
         
           
             
               
                 
                   
                     [ 
                     
                       
                         
                           x 
                         
                       
                       
                         
                           y 
                         
                       
                     
                     ] 
                   
                   = 
                   
                     
                       
                         S 
                         ⁡ 
                         
                           ( 
                           θ 
                           ) 
                         
                       
                       ⁡ 
                       
                         [ 
                         
                           
                             
                               z 
                             
                           
                           
                             
                               y 
                             
                           
                         
                         ] 
                       
                     
                     + 
                     
                       
                         [ 
                         
                           
                             
                               
                                 c 
                                 x 
                               
                             
                           
                           
                             
                               
                                 c 
                                 y 
                               
                             
                           
                         
                         ] 
                       
                       . 
                     
                   
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
           
         
       
     
     The four vertices in equation (2) defining the sensor footprint  104  can be transformed into global coordinates using equation (4). The sensor footprint is defined by four variables (c x ,c y ,θ,φ). The first two variables are the projection of the sensor position onto the environment plane, and the last two parameters are the horizontal and vertical angular variables. Other sensors may have different footprint shapes, with the footprint shape and size depending on the sensor orientation. 
     In most practical embodiments, the position parameters are updated on a relatively slow time scale because these parameters correspond to the physical position of the sensor, while the angular variables are updated on a relatively fast time scale because the angles can quickly change values. However, in some embodiments, position parameters and angle parameters might change values at the same time scale, or angle parameters might change values at a slower time scale. 
     Subadditive Combination of Overlapping Sensors 
     Assume that sensor i provides a resolution r i  in the footprint F i , i=1, . . . , n. The problem is to model the resolution obtained in an intersection of complete or partial overlapping footprints. The best, and unrealistically optimistic, situation is for the overall resolution to be the sum of the individual resolutions. The worst, and unrealistically pessimistic, situation is for the overall resolution to equal the maximum of the individual sensor resolutions. The actual overall resolution is somewhere between these extremes. 
     That is, if
 
 r=[r   1   r   2    . . . r   N ]  (5)
 
is a vector of the resolutions achieved by N sensors, the overall resolution res(r) obtained at points in the intersection of the sensor footprints satisfies the following inequalities
 
     
       
         
           
             
               
                 
                   
                     
                       max 
                       i 
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       r 
                       i 
                     
                   
                   ≤ 
                   
                     res 
                     ⁡ 
                     
                       ( 
                       r 
                       ) 
                     
                   
                   ≤ 
                   
                     
                       r 
                       1 
                     
                     + 
                     … 
                     + 
                     
                       
                         r 
                         N 
                       
                       . 
                     
                   
                 
               
               
                 
                   ( 
                   6 
                   ) 
                 
               
             
           
         
       
     
     One example of a function that satisfies this property is the l p  norm of the vector r, 1&lt;p&lt;∞, 
                            r        p     ⁢     =   def     ⁢       (       r   l   p     +     …   ⁢           ⁢     r   N   p         )       1   /   p         ,           (   7   )               
where 1&lt;p&lt;∞. When p=1, the l p  norm equals the upper bound in equation (6). When p=∞, the l p  norm equals the lower bound in equation (6). Thus, a particular example of a subadditive model for the resolution obtained by overlapping sensors is the l p  norm of a vector of individual resolutions, where 1&lt;p&lt;∞. Other embodiments can use different subadditive functions to model how images of different resolutions are combined.
 
     Objective Function and Optimization 
     Let φ d (q) be the desired resolution defined at every point q  401  in the environment  400 . Let x j  be a vector of the position variables of all of the sensors at time j. Let ψ j  and θ j  be vectors corresponing to the vertical (declination) and horizontal (azimuth) angular variables at time j, respectively, of all of the sensors. Let R i  be the resolution provided by the i th  sensor at all points in its footprint F i , which is defined by sensor variables (cx i ,cy i ,θ i ,ψ i ) as 
                       R   i     ⁡     (       cx   i     ,     cy   i     ,     θ   i     ,     ψ   i     ,   q     )       =     {               K       H   2     ⁡     [     1   +       tan   2     ⁡     (     ψ   i     )         ]         ,           q   ∈       F   i     ⁡     (       cx   i     ,     cy   i     ,     θ   i     ,     ψ   i       )                   0   ,         otherwise         ,               (   8   )               
where K is a sensor constant that depends on the number of pixels in an acquired image. If all of the sensors have the same value of K, then the value is unimportant for the optimization described below.
 
     At any time j, the objective function we minimize is a difference between the desired resolution and an achieved resolution up to time j−1 according to the following function: 
                         G   j     ⁡     (     x   ,   θ   ,   ψ     )       =       ∫   Q     ⁢       f   (         φ   d     ⁡     (   q   )       -       [         φ     j   -   1     p     ⁡     (   q   )       +       ∑   i     ⁢           ⁢       (       R   i     ⁡     (       cx   i     ,     cy   i     ,     θ   i     ,     ψ   i     ,   q     )       )     p         ]       1   /   p         )     ⁢           ⁢     ⅆ   q           ,           (   9   )               
where φ j−1 (q) is the resolution achieved by the sensors up to time j−1, p defines the norm used to model a subadditive combination of overlapping footprints, and f(x) is a penalty function that penalizes deviation from the desired resolution.
 
     For example, in one embodiment, f(x)=x 2 . This penalty function penalizes the achieved resolution when the resolution is lower or greater than the desired resolution. This forces the sensors to move to a different area of the environment when some of the sensors have been mapped to a sufficient resolution. 
     In another embodiment, 
     
       
         
           
             
               f 
               ⁡ 
               
                 ( 
                 x 
                 ) 
               
             
             = 
             
               { 
               
                 
                   
                     
                       
                         
                           x 
                           2 
                         
                         , 
                       
                     
                     
                       
                         x 
                         ≥ 
                         0 
                       
                     
                   
                   
                     
                       
                         0 
                         , 
                       
                     
                     
                       
                         x 
                         &lt; 
                         0 
                       
                     
                   
                 
                 . 
               
             
           
         
       
     
     This penalty function penalizes the achieved resolution only when it has not attained the desired resolution, which enables the sensor to continue improving the resolution of the imaged area beyond the pre-specified desired resolution. Of course, other embodiments may use other penalty functions. 
     Path Planning 
       FIG. 6  shows a method for path planning according to embodiments of the invention. By definition, the initial achieved resolution φ 0 (q) is identically zero. 
     A gradient-based optimization is described by the following initialization and iterative steps. At each time j, a complete gradient-based minimization with respect to the angle parameters of the sensors is performed. However, sensor positions are updated using only a single gradient step. The reason is that after the sensors have moved and acquired new data, the objective function has changed. 
     Initialization 
     Given the desired resolution φ d (q), and a vector x 0  of initial sensor positions, initial sensor angles are determined  605  by the following optimization  611   
     
       
         
           
             
               
                 
                   
                     θ 
                     0 
                   
                   , 
                   
                     
                       ψ 
                       0 
                     
                     = 
                     
                       arg 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         
                           min 
                           
                             θ 
                             , 
                             ψ 
                           
                         
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         
                           
                             
                               G 
                               0 
                             
                             ⁡ 
                             
                               ( 
                               
                                 
                                   x 
                                   0 
                                 
                                 , 
                                 θ 
                                 , 
                                 ψ 
                               
                               ) 
                             
                           
                           . 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   11 
                   ) 
                 
               
             
           
         
       
     
     The initial position gradient g 0  is the gradient with respect to x of G 0 (x, θ 0 , ψ 0 ) evaluated at x 0 . 
     Iteration  650  j=1, 2, . . . at each Sensor for each Time Step 
     Acquire  610  images  601  from all sensors  100 , and update  620  an achieved resolution  621  according to 
     
       
         
           
             
               
                 
                   
                     
                       φ 
                       j 
                     
                     ⁡ 
                     
                       ( 
                       
                         q 
                         , 
                         
                           x 
                           
                             j 
                             - 
                             1 
                           
                         
                         , 
                         
                           θ 
                           
                             j 
                             - 
                             1 
                           
                         
                         , 
                         
                           ψ 
                           
                             j 
                             - 
                             1 
                           
                         
                       
                       ) 
                     
                   
                   = 
                   
                     
                       
                         [ 
                         
                           
                             
                               φ 
                               
                                 j 
                                 - 
                                 1 
                               
                               p 
                             
                             ⁡ 
                             
                               ( 
                               q 
                               ) 
                             
                           
                           + 
                           
                             ( 
                             
                               
                                 ∑ 
                                 i 
                               
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 
                                   ( 
                                   
                                     
                                       R 
                                       i 
                                     
                                     ⁡ 
                                     
                                       ( 
                                       
                                         
                                           cx 
                                           
                                             j 
                                             - 
                                             1 
                                           
                                           i 
                                         
                                         , 
                                         
                                           cy 
                                           
                                             j 
                                             - 
                                             1 
                                           
                                           i 
                                         
                                         , 
                                         
                                           θ 
                                           
                                             j 
                                             - 
                                             1 
                                           
                                           i 
                                         
                                         , 
                                         
                                           ψ 
                                           
                                             j 
                                             - 
                                             1 
                                           
                                           i 
                                         
                                         , 
                                         q 
                                       
                                       ) 
                                     
                                   
                                   ) 
                                 
                                 p 
                               
                             
                             ) 
                           
                         
                         ] 
                       
                       
                         1 
                         / 
                         p 
                       
                     
                     . 
                   
                 
               
               
                 
                   ( 
                   12 
                   ) 
                 
               
             
           
         
       
     
     Moving  630  the set of sensors to a next position and orientation of the sensor based on the achieved resolution and the desired resolution. The moving is in a direction of the negative position gradient  631 
 
 x   j   =x   j−1   −αg   j−1   (13)
 
where α is a step size, and g j−1  is the position gradient at a previous time evaluated at position x j−1 . It should be understood that the moving to the next position and orientation can be a “null” move, i.e., the sensor remains in place.
 
     Update  640  the sensor angular parameters and the position gradient  641  according to 
                           ⁢       θ   j     ,       ψ   j     =     arg   ⁢           ⁢       min     θ   ,   ψ       ⁢           ⁢       G   j     ⁡     (       x   j     ,   θ   ,   ψ     )                       (   14   )                   g   j     =     gradient   ⁢           ⁢   with   ⁢           ⁢   respect   ⁢           ⁢   to   ⁢           ⁢   x   ⁢           ⁢   of   ⁢           ⁢       G   j     ⁡     (     x   ,     θ   j     ,     ψ   j       )       ⁢           ⁢   evaluated   ⁢           ⁢   at   ⁢           ⁢     x   3         ,                           
and iterate for the next time instant j=j+1.
 
     Although the invention has been described by way of examples of preferred embodiments, it is to be understood that various other adaptations and modifications can be made within the spirit and scope of the invention. Therefore, it is the object of the appended claims to cover all such variations and modifications as come within the true spirit and scope of the invention.