Claims:1. A processor implemented method (200) comprising:
discretizing a 3-Dimensional (3D) Euclidean navigation space of an aerial vehicle for tractability by imposing a grid of a plurality of unit cells, on the 3D Euclidean navigation space (202);
identifying a flight corridor in the 3-D Euclidean navigation space defined between a minimum separation constraint being a pre-defined minimum distance from a target under consideration and a maximum separation constraint being a pre-defined maximum distance from the target under consideration (204);
identifying a current node, a grandparent node and a parent node associated with the current node, in a partial path generated offline for the aerial vehicle in the flight corridor (206); and
iteratively, identifying a neighbor node for the current node to augment the partial path for surveillance of the target under consideration (208), by:
identifying at least one potential neighbor node of the current node satisfying a line of sight condition with the parent node or satisfying a collinear condition with the current node and the parent node (208a);
in the event that the parent node, the current node and the potential neighbor node are non-collinear, evaluating a minimum route leg length constraint between the parent node and the current node to identify one of the at least one potential neighbor node as the neighbor node for augmenting the partial path, the minimum route leg length constraint being a pre-defined minimum distance, wherein the augmented partial path from the current node to the at least one potential neighbor node is a straight segment (208b);
in the event that one of the minimum route leg length constraint; the line of sight condition or the collinear condition is satisfied by the at least one potential neighbor node, further evaluating a maximum turn angle constraint consistency for the at least one potential neighbor node with respect to the grandparent node and further evaluating with respect to the parent node in the event that the evaluation with respect to the grandparent node fails, to identify another one of the at least one potential neighbor node as the neighbor node for augmenting the partial path, the maximum turn angle constraint being a maximum turning angle permissible for the aerial vehicle (208c);
backtracking to at least one prior node along the augmented partial path until a previous iteration, in the event that either the maximum turn angle constraint consistency or the minimum route leg length constraint fails for each of the at least one potential neighbor nodes (208d); and
identifying a backtracked node from the at least one prior node on a backtracked path as the current node for augmenting the partial path (208e).

2. The processor implemented method of claim 1, wherein the step of identifying a neighbor node for the current node to augment the partial path further comprises:
evaluating a storage constraint for each of the at least one potential neighbor node, in the event that a coverage hole is encountered along the augmented partial path; the evaluation being based on potential augmented partial paths within the coverage hole having identical entry point into the coverage hole and the storage constraint being a pre-defined upper bounded length for the augmented partial path within the coverage hole (208f); and
backtracking to at least one prior node along the augmented partial path until a previous iteration, in the event that the storage constraint consistency fails for each of the at least one potential neighbor nodes (208g).

3. The processor implemented method of claim 2, wherein the flight corridor is a cylindrical annulus around the target under consideration in 3-Dimensional space.

4. The processor implemented method of claim 2, wherein the pre-defined minimum distance associated with the minimum route leg length constraint is based on inertia of motion, such that the aerial vehicle moves along a straight path for the pre-defined minimum distance based on inertia before making a turn.

5. The processor implemented method of claim 2, wherein the pre-defined upper bounded length associated with the storage constraint is based on a constant speed of the aerial vehicle, frame rate of an onboard visual capturing device, frame size and amount of permissible onboard storage.

6. The processor implemented method of claim 2, wherein backtracking to at least one
prior node along the augmented partial path until a previous iteration, in the event that the storage constraint consistency fails comprises:
computing distance of the current node from each of the finite boundary points of the coverage hole;
computing cumulative distance of the current node from the entry point within the coverage hole;
identifying a potential backtracked node in the augmented partial path at a distance indicative of the overflow based on the pre-defined upper bounded length, the computed shortest distance of the current node from the finite boundary points and the computed cumulative distance; and
backtracking to a grid corner closest to the potential backtracked node.

7. The processor implemented method of claim 2 further comprising storing data associated with the surveillance of the target under consideration, onboard in the event that the storage constraint fails (210).

8. A system (100) comprising:
one or more data storage devices (102) operatively coupled to one or more hardware processors (104) and configured to store instructions configured for execution by the one or more hardware processors to:
discretize a 3-Dimensional (3D) Euclidean navigation space of an aerial vehicle for tractability by imposing a grid of a plurality of unit cells, on the 3D Euclidean navigation space;
identify a flight corridor in the 3-D Euclidean navigation space defined between a minimum separation constraint being a pre-defined minimum distance from a target under consideration and a maximum separation constraint being a pre-defined maximum distance from the target under consideration;
identify a current node, a grandparent node and a parent node associated with the current node, in a partial path generated offline for the aerial vehicle in the flight corridor; and
iteratively, identify a neighbor node for the current node to augment the partial path for surveillance of the target under consideration, by:
identifying at least one potential neighbor node of the current node satisfying a line of sight condition with the parent node or satisfying a collinear condition with the current node and the parent node;
in the event that the parent node, the current node and the potential neighbor node are non-collinear, evaluating a minimum route leg length constraint between the parent node and the current node to identify one of the at least one potential neighbor node as the neighbor node for augmenting the partial path, the minimum route leg length constraint being a pre-defined minimum distance, wherein the augmented partial path from the current node to the at least one potential neighbor node is a straight segment;
in the event that one of the minimum route leg length constraint; the line of sight condition or the collinear condition is satisfied by the at least one potential neighbor node, further evaluating a maximum turn angle constraint consistency for the at least one potential neighbor node with respect to the grandparent node and further evaluating with respect to the parent node in the event that the evaluation with respect to the grandparent node fails, to identify another one of the at least one potential neighbor node as the neighbor node for augmenting the partial path, the maximum turn angle constraint being a maximum turning angle permissible for the aerial vehicle;
backtracking to at least one prior node along the augmented partial path until a previous iteration, in the event that either the maximum turn angle constraint consistency or the minimum route leg length constraint fails for each of the at least one potential neighbor nodes; and
identifying a backtracked node from the at least one prior node on a backtracked path as the current node for augmenting the partial path.

9. The system of claim 8, wherein the one or more hardware processors are further configured to identify a neighbor node for the current node to augment the partial path by:
evaluating a storage constraint for each of the at least one potential neighbor node, in the event that a coverage hole is encountered along the augmented partial path; the evaluation being based on potential augmented partial paths within the coverage hole having identical entry point into the coverage hole and the storage constraint being a pre-defined upper bounded length for the augmented partial path within the coverage hole; and
backtracking to at least one prior node along the augmented partial path until a previous iteration, in the event that the storage constraint consistency fails for each of the at least one potential neighbor nodes.

10. The system of claim 9, wherein the flight corridor is a cylindrical annulus around the target under consideration in 3-Dimensional space.

11. The system of claim 9, wherein the pre-defined minimum distance associated with the minimum route leg length constraint is based on inertia of motion, such that the aerial vehicle moves along a straight path for the pre-defined minimum distance based on inertia before making a turn.

12. The system of claim 9, wherein the pre-defined upper bounded length associated with the storage constraint is based on a constant speed of the aerial vehicle, frame rate of an onboard visual capturing device, frame size and amount of permissible onboard storage.

13. The system of claim 9, wherein the one or more hardware processors are further configured to backtrack to at least one prior node along the augmented partial path until a previous iteration, in the event that the storage constraint consistency fails by:
computing distance of the current node from each of the finite boundary points of the coverage hole;
computing cumulative distance of the current node from the entry point within the coverage hole;
identifying a potential backtracked node in the augmented partial path at a distance indicative of the overflow based on the pre-defined upper bounded length, the computed shortest distance of the current node from the finite boundary points and the computed cumulative distance; and
backtracking to a grid corner closest to the potential backtracked node.

14. The system of claim 9, wherein the one or more hardware processors are further configured to store data associated with the surveillance of the target under consideration, onboard in the event that the storage constraint fails.
, Description:FORM 2

THE PATENTS ACT, 1970
(39 of 1970)
&
THE PATENT RULES, 2003

COMPLETE SPECIFICATION
(See Section 10 and Rule 13)

Title of invention:
AERIAL PATH PLANNING FOR MAINTAINING TRANSMISSION CONTINUITY IN PRESENCE OF COVERAGE HOLES

Applicant:
Tata Consultancy Services Limited
A company Incorporated in India under the Companies Act, 1956
Having address:
Nirmal Building, 9th Floor,
Nariman Point, Mumbai 400021,
Maharashtra, India

The following specification particularly describes the embodiments and the manner in which it is to be performed.

TECHNICAL FIELD
The embodiments herein generally relate to aerial path planning, and more particularly to systems and methods for maintaining transmission continuity in presence of coverage holes.

BACKGROUND
Usage of aerial vehicles such as unmanned aerial vehicles (UAVs) for maintenance inspections of critical utility infrastructures, is rapidly emerging as a popular option. Installations for critical utility infrastructures generally have a characteristic of being long and linear and are mostly vast in terms of size and length probably running into hundreds of kilometers. Maintenance, both preventive and breakdown, is typically a costly legal responsibility towards public safety. However, the amount of surveillance data captured in the form of video or images is typically huge, due to vastness of infrastructures. Since so much data cannot be stored, it needs to be transmitted to a storage device on-ground. For continuous transmission, a path is desired along which maximal wireless signal coverage is available. Design of such path gets complex due to the fact that in vast surveillance areas, there may be sub-areas which are no-coverage zones. The no-coverage zones regions arise because of absence of a base station in the vicinity. Conventional methods of aerial path planning address generic conditions like shortest path however transmission continuity remains a challenge. The methods may not address coverage holes through which passage is restrained but not forbidden, thereby resulting in loss of captured data during the passage of the drones through coverage holes. Also, distance cost needs to be minimized in view of obstacles that may be entailed along the path.

SUMMARY
Embodiments of the present disclosure present technological improvements as solutions to one or more of the above-mentioned technical problems recognized by the inventors in conventional systems.
In an aspect, there is provided a processor implemented method comprising: discretizing a 3-Dimensional (3D) Euclidean navigation space of an aerial vehicle for tractability by imposing a grid of a plurality of unit cells, on the 3D Euclidean navigation space; identifying a flight corridor in the 3-D Euclidean navigation space defined between a minimum separation constraint being a pre-defined minimum distance from a target under consideration and a maximum separation constraint being a pre-defined maximum distance from the target under consideration; identifying a current node, a grandparent node and a parent node associated with the current node, in a partial path generated offline for the aerial vehicle in the flight corridor; and iteratively, identifying a neighbor node for the current node to augment the partial path for surveillance of the target under consideration by performing a set of sub-steps as described herein below.
Firstly, at least one potential neighbor node of the current node satisfying a line of sight condition with the parent node or satisfying a collinear condition with the current node and the parent node may be identified. In the event that the parent node, the current node and the potential neighbor node are non-collinear, a minimum route leg length constraint may be evaluated between the parent node and the current node to identify one of the at least one potential neighbor node as the neighbor node for augmenting the partial path, the minimum route leg length constraint being a pre-defined minimum distance, wherein the augmented partial path from the current node to the at least one potential neighbor node is a straight segment. In the event that one of the minimum route leg length constraint; the line of sight condition or the collinear condition is satisfied by the at least one potential neighbor node, a maximum turn angle constraint consistency may be further evaluated for the at least one potential neighbor node with respect to the grandparent node and further evaluating with respect to the parent node in the event that the evaluation with respect to the grandparent node fails, to identify another one of the at least one potential neighbor node as the neighbor node for augmenting the partial path, the maximum turn angle constraint being a maximum turning angle permissible for the aerial vehicle. The method may comprise backtracking to at least one prior node along the augmented partial path until a previous iteration, in the event that either the maximum turn angle constraint consistency or the minimum route leg length constraint fails for each of the at least one potential neighbor nodes. A backtracked node from the at least one prior node on a backtracked path may be identified as the current node for augmenting the partial path in a next iteration.
In another aspect, there is provided a system comprising: one or more data storage devices operatively coupled to the one or more processors and configured to store instructions configured for execution by the one or more processors to: discretize a 3-Dimensional (3D) Euclidean navigation space of an aerial vehicle for tractability by imposing a grid of a plurality of unit cells, on the 3D Euclidean navigation space; identify a flight corridor in the 3-D Euclidean navigation space defined between a minimum separation constraint being a pre-defined minimum distance from a target under consideration and a maximum separation constraint being a pre-defined maximum distance from the target under consideration; identify a current node, a grandparent node and a parent node associated with the current node, in a partial path generated offline for the aerial vehicle in the flight corridor; and iteratively, identify a neighbor node for the current node to augment the partial path for surveillance of the target under consideration, by: identifying at least one potential neighbor node of the current node satisfying a line of sight condition with the parent node or satisfying a collinear condition with the current node and the parent node; in the event that the parent node, the current node and the potential neighbor node are non-collinear, evaluating a minimum route leg length constraint between the parent node and the current node to identify one of the at least one potential neighbor node as the neighbor node for augmenting the partial path, the minimum route leg length constraint being a pre-defined minimum distance, wherein the augmented partial path from the current node to the at least one potential neighbor node is a straight segment; in the event that one of the minimum route leg length constraint; the line of sight condition or the collinear condition is satisfied by the at least one potential neighbor node, further evaluating a maximum turn angle constraint consistency for the at least one potential neighbor node with respect to the grandparent node and further evaluating with respect to the parent node in the event that the evaluation with respect to the grandparent node fails, to identify another one of the at least one potential neighbor node as the neighbor node for augmenting the partial path, the maximum turn angle constraint being a maximum turning angle permissible for the aerial vehicle; backtracking to at least one prior node along the augmented partial path until a previous iteration, in the event that either the maximum turn angle constraint consistency or the minimum route leg length constraint fails for each of the at least one potential neighbor nodes; and identifying a backtracked node from the at least one prior node on a backtracked path as the current node for augmenting the partial path in a next iteration.
In yet another aspect, there is provided a computer program product comprising a non-transitory computer readable medium having a computer readable program embodied therein, wherein the computer readable program, when executed on a computing device, causes the computing device to: discretize a 3-Dimensional (3D) Euclidean navigation space of an aerial vehicle for tractability by imposing a grid of a plurality of unit cells, on the 3D Euclidean navigation space; identify a flight corridor in the 3-D Euclidean navigation space defined between a minimum separation constraint being a pre-defined minimum distance from a target under consideration and a maximum separation constraint being a pre-defined maximum distance from the target under consideration; identify a current node, a grandparent node and a parent node associated with the current node, in a partial path generated offline for the aerial vehicle in the flight corridor; and iteratively, identify a neighbor node for the current node to augment the partial path for surveillance of the target under consideration, by: identifying at least one potential neighbor node of the current node satisfying a line of sight condition with the parent node or satisfying a collinear condition with the current node and the parent node; in the event that the parent node, the current node and the potential neighbor node are non-collinear, evaluating a minimum route leg length constraint between the parent node and the current node to identify one of the at least one potential neighbor node as the neighbor node for augmenting the partial path, the minimum route leg length constraint being a pre-defined minimum distance, wherein the augmented partial path from the current node to the at least one potential neighbor node is a straight segment; in the event that one of the minimum route leg length constraint; the line of sight condition or the collinear condition is satisfied by the at least one potential neighbor node, further evaluating a maximum turn angle constraint consistency for the at least one potential neighbor node with respect to the grandparent node and further evaluating with respect to the parent node in the event that the evaluation with respect to the grandparent node fails, to identify another one of the at least one potential neighbor node as the neighbor node for augmenting the partial path, the maximum turn angle constraint being a maximum turning angle permissible for the aerial vehicle; backtracking to at least one prior node along the augmented partial path until a previous iteration, in the event that either the maximum turn angle constraint consistency or the minimum route leg length constraint fails for each of the at least one potential neighbor nodes; and identifying a backtracked node from the at least one prior node on a backtracked path as the current node for augmenting the partial path in a next iteration.
In an embodiment of the present disclosure, the one or more hardware processors are further configured to identify a neighbor node for the current node to augment the partial path by: evaluating a storage constraint for each of the at least one potential neighbor node, in the event that a coverage hole is encountered along the augmented partial path; the evaluation being based on potential augmented partial paths within the coverage hole having identical entry point into the coverage hole and the storage constraint being a pre-defined upper bounded length for the augmented partial path within the coverage hole; and backtracking to at least one prior node along the augmented partial path until a previous iteration, in the event that the storage constraint consistency fails for each of the at least one potential neighbor nodes.
In an embodiment of the present disclosure, the flight corridor is a cylindrical annulus around the target under consideration in 3-Dimensional space.
In an embodiment of the present disclosure, the pre-defined minimum distance associated with the minimum route leg length constraint is based on inertia of motion, such that the aerial vehicle moves along a straight path for the pre-defined minimum distance based on inertia before making a turn.
In an embodiment of the present disclosure, the pre-defined upper bounded length associated with the storage constraint is based on a constant speed of the aerial vehicle, frame rate of an onboard visual capturing device, frame size and amount of permissible onboard storage.
It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory only and are not restrictive of the embodiments of the present disclosure, as claimed.
In an embodiment of the present disclosure, the one or more hardware processors are further configured to backtrack to at least one prior node along the augmented partial path until a previous iteration, in the event that the storage constraint consistency fails by: computing distance of the current node from each of the finite boundary points of the coverage hole; computing cumulative distance of the current node from the entry point within the coverage hole; identifying a potential backtracked node in the augmented partial path at a distance indicative of the overflow based on the pre-defined upper bounded length, the computed shortest distance of the current node from the finite boundary points and the computed cumulative distance; and backtracking to a grid corner closest to the potential backtracked node.

BRIEF DESCRIPTION OF THE DRAWINGS
The embodiments herein will be better understood from the following detailed description with reference to the drawings, in which:
FIG.1 illustrates an exemplary block diagram of a system for aerial path planning for maintaining transmission continuity in presence of coverage holes, in accordance with an embodiment of the present disclosure;
FIG.2 is an exemplary flow diagram illustrating a computer implemented method for aerial path planning for maintaining transmission continuity in presence of coverage holes, in accordance with an embodiment of the present disclosure;
FIG.3 illustrates an exemplary coverage hole in presence of multiple wireless receivers;
FIG.4A and FIG.4B provide an illustrative comparison between a discrete shortest path using square grid as known in the art and an actual continuous shortest path;
FIG.5 illustrates a flight corridor identified in 3-Dimensional (3D) Euclidean navigation space of an aerial vehicle based on a minimum separation constraint and a maximum separation constraint in accordance with the present disclosure;
FIG.6 illustrates node nomenclature for a shortest path algorithm, in accordance with an embodiment of the present disclosure; and
FIG.7 illustrates backtracking to a prior node within a coverage hole, in accordance with an embodiment of the present disclosure.
It should be appreciated by those skilled in the art that any block diagram herein represent conceptual views of illustrative systems embodying the principles of the present subject matter. Similarly, it will be appreciated that any flow charts, flow diagrams, state transition diagrams, pseudo code, and the like represent various processes which may be substantially represented in computer readable medium and so executed by a computing device or processor, whether or not such computing device or processor is explicitly shown.

DETAILED DESCRIPTION
The embodiments herein and the various features and advantageous details thereof are explained more fully with reference to the non-limiting embodiments that are illustrated in the accompanying drawings and detailed in the following description. The examples used herein are intended merely to facilitate an understanding of ways in which the embodiments herein may be practiced and to further enable those skilled in the art to practice the embodiments herein. Accordingly, the examples should not be construed as limiting the scope of the embodiments herein.
The words "comprising," "having," "containing," and "including," and other forms thereof, are intended to be equivalent in meaning and be open ended in that an item or items following any one of these words is not meant to be an exhaustive listing of such item or items, or meant to be limited to only the listed item or items.
It must also be noted that as used herein and in the appended claims, the singular forms "a," "an," and "the" include plural references unless the context clearly dictates otherwise. Although any systems and methods similar or equivalent to those described herein can be used in the practice or testing of embodiments of the present disclosure, the preferred, systems and methods are now described.
Some embodiments of this disclosure, illustrating all its features, will now be discussed in detail. The disclosed embodiments are merely exemplary of the disclosure, which may be embodied in various forms.
Before setting forth the detailed explanation, it is noted that all of the discussion below, regardless of the particular implementation being described, is exemplary in nature, rather than limiting.
In the context of the present disclosure, the expression “aerial vehicle” may refer to a fixed-wing vehicle such as unmanned aerial vehicles (UAVs) or drones, gliders, airplanes, and the like.
Fixed-wing vehicles are required to make a turning maneuver less than or equal to a predetermined maximum turning angle. Planning an aerial path in the presence of coverage holes or obstacles keeping in mind the turn angle constraint was addressed by the applicant in a previous patent application no. 201721001481 filed on 13 January, 2017 at the Indian Patent Office, parts of which is incorporated herein by reference. The present disclosure provides a path panning algorithm for aerial vehicles that are used particularly for monitoring of long linear infrastructures that involves surveillance data in the form of video or images. Given the limited storage capacity on board, if a storage device is full, overflow may result in parts of captured surveillance data being lost and hence not being available later for analysis. The present disclosure thus provides systems and methods that ensure transmission continuity of data from aerial vehicles even in presence of radio coverage holes by addressing not just the turn angle constraint but a plurality of inter-related constraints, particularly a storage constraint.
Referring now to the drawings, and more particularly to FIGS. 1 through 7, where similar reference characters denote corresponding features consistently throughout the figures, there are shown preferred embodiments and these embodiments are described in the context of the following exemplary system and method.
FIG.1 illustrates an exemplary block diagram of a system 100 for maintaining transmission continuity in presence of coverage holes, in accordance with an embodiment of the present disclosure. In an embodiment, the system 100 includes one or more processors 104, communication interface device(s) or input/output (I/O) interface(s) 106, and one or more data storage devices or memory 102 operatively coupled to the one or more processors 104. The one or more processors 104 that are hardware processors can be implemented as one or more microprocessors, microcomputers, microcontrollers, digital signal processors, central processing units, state machines, graphics controllers, logic circuitries, and/or any devices that manipulate signals based on operational instructions. Among other capabilities, the processor(s) are configured to fetch and execute computer-readable instructions stored in the memory. In an embodiment, the system 100 can be implemented in a variety of computing systems, such as laptop computers, notebooks, hand-held devices, workstations, mainframe computers, servers, a network cloud and the like.
The I/O interface device(s) 106 can include a variety of software and hardware interfaces, for example, a web interface, a graphical user interface, and the like and can facilitate multiple communications within a wide variety of networks N/W and protocol types, including wired networks, for example, LAN, cable, etc., and wireless networks, such as WLAN, cellular, or satellite. In an embodiment, the I/O interface device(s) can include one or more ports for connecting a number of devices to one another or to another server.
The memory 102 may include any computer-readable medium known in the art including, for example, volatile memory, such as static random access memory (SRAM) and dynamic random access memory (DRAM), and/or non-volatile memory, such as read only memory (ROM), erasable programmable ROM, flash memories, hard disks, optical disks, and magnetic tapes. In an embodiment, one or more modules (not shown) of the system 100 can be stored in the memory 102.
FIG.2 is an exemplary flow diagram illustrating a computer implemented method 200 for maintaining transmission continuity in presence of coverage holes, in accordance with an embodiment of the present disclosure. In an embodiment, the system 100 comprises one or more data storage devices or memory 102 operatively coupled to the one or more processors 104 and is configured to store instructions configured for execution of steps of the method 200 by the one or more processors 104.
Formal specification of any optimization problem entails specification of decision variables, the cost/objective as a function of the variables, and constraints wherever applicable. In terms of the decision variables, there is only one set involved, the 3D instantaneous location of the UAV: ‹x,y,z›. If the altitude is assumed constant, then the location is a 2-tuple, formed by latitude and longitude. In terms of constraints, the present disclosure focusses on a plurality of constraints, viz., minimum and maximum separation constraints, minimum route leg length constraint, storage constraint and turn angle constraint.
Linear infrastructures generally require that no man, machine or any other artificial system ever intrude within a pre-defined vicinity of the infrastructure. Such restricted area is called Right of Way. In case of unmanned flights, flying too close to the infrastructure and sudden control failure of the aerial vehicle such as UAV may also mean that the aerial vehicle or a part of it may fall on the infrastructure and damage it, which may lead to interruption of critical supply that the particular infrastructure bears. Further, specifically in the case of power grid corridors, flying too close to HV transmission lines may lead to electromagnetic interference between the electrical circuits of the aerial vehicle, and power lines. Such interference may lead to corruption of internal flight control data over internal wires, and eventual failure of pilot flights. The minimum separation constraint, in the context of the present disclosure, refers to a pre-defined minimum distance from a target under consideration.
A visual capturing device such as a camera mounted in the belly of the aerial vehicle may be used to perform a remote surveillance task involving capturing images of long linear infrastructures. A visible range digital camera, using any technology has a performance limit, fundamentally due to its usage of lens system, and a finite-sized charge-coupled device (CCD) or complementary metal-oxide semiconductor (CMOS) backplane. It is understood that if the distance between the object being imaged, and a digital visible-range camera is more than a specific distance known as Depth of Field, then the object cannot be properly imaged or will be as hazy as underlying background, typically earth's surface or terrestrial terrain. The application demands that the foreground object of interest be reasonably sharp and distinct from background, for computer vision techniques to be applied for segmenting out thinner infrastructures against the vast and wide background. The maximum separation constraint, in the context of the present disclosure, refers to a pre-defined maximum distance from the target under consideration.
In the context of the present disclosure, a minimum route leg length constraint forces the path taken by the aerial vehicle to be a straight segment for a pre-defined minimum distance before initiating a turn. The pre-defined minimum distance may be based on inertia of motion, such that the aerial vehicle moves along a straight path for the pre-defined minimum distance based on inertia before making a turn.
In the context of the present disclosure, a turn angle constraint forces a generated path to make a turning maneuver, less than or equal to a maximum turning angle permissible for the aerial vehicle. The turn angle constraint avoids possibility of an aerodynamic stall during motion of a fixed wing vehicle.
In the context of the present disclosure, a storage constraint arises out of a requirement for maximization of cellular coverage. In vast, non-urban terrain through which critical infrastructures under surveillance may pass, such as area between two cities, there are expected to be multiple regions which are coverage holes. The multiple regions arise since there is no base station in the vicinity. FIG.3 illustrates an exemplary coverage hole in presence of multiple wireless receivers. More specifically, in practical scenarios, most wireless receivers cannot recover signal if the Signal-to-noise (SNR) is too low (lower bound). Accordingly, if closest access point is situated at a distance beyond dminSNR, then the aerial vehicle is in practically zero coverage zone. It is not possible to altogether avoid the zero coverage zones while designing an optimal path. In non-urban scenario, unless infrastructural systems run close to highways, the cellular coverage is expected to be quite sparse along their length. Having very few access points in vicinity means if the path planning focuses only on maximizing coverage, a solution will either not be feasible, or will have to run close to e.g. highways. In the latter case, the (main) path length cost will be higher. Hence there is an inherent tradeoff between optimizing for path length and optimizing for cellular coverage. In the event that an aerial path leads through coverage holes, the surveillance data may be stored on-board. The stored video may then be transmitted later, when good SNR conditions prevail. Given limited storage, if the storage device becomes full, parts of the surveillance data may get lost due to overflow. In order to avoid overflow while storing, the systems of the present disclosure may force the methods to only consider options where a segment of the aerial path lying in a specific coverage hole has a pre-defined upper-bounded length. The pre-defined upper bounded length associated with the storage constraint is based on a constant speed of the aerial vehicle, frame rate of an onboard visual capturing device, frame size and amount of permissible onboard storage. For the entire aerial path, if there are ‘2*Z’ locations along the path, every successive pair of which implies a coverage hole, then
?i ? {1, ……., z}: ||Pz2.i – Pz(2.i - 1)|| = dzero, wherein P represents path and dzero represents the upper-bounded length driven by the limit of onboard storage within each coverage hole.
Distance cost is a mandatory cost component in all path planning algorithms that have arisen till date. It represents the length, in Euclidean space, of an optimal path undertaken by the aerial vehicle. The distance cost directly correlates to the limited battery power of the aerial vehicle, which is not fuel-driven. At a certain speed of the aerial vehicle, against an assumed constant wind speed, the energy of a charged battery may last only a certain distance. To try to maximize the mission, given that application required tens of kilometers to be remotely surveyed, the distance cost has to be minimized. In a discrete graph model of the navigation space, the solution reduces to finding the shortest path in Euclidean space (Euclidean shortest path).
For any path in discrete grid, piecewise-linear path assumption is a valid assumption also because of the shortest length, Lmin constraint. In such a case, insertion of additional variables to denote turning points of the aerial vehicle and sum of Euclidean distances between such successive turning points, is a direct measure of such cost. Let PTi; i ? 1, …, T be the coordinate tuple of each turning point along a path in a coordinate system such as say, world coordinate system (WCS). Then,

Path cost= ?_(i=1)^(T-1)¦?||P_(T_(i+1) )-P_(T_i ) || ?

wherein || . || denotes an appropriate norm, typically being L2 (Least squares) norm.
As known in the art, A* search algorithm has been used as a search method of choice in real applications due to its simplicity and optimality guarantee under admissibility criterion. However, in geographical applications in which the environment is continuous, a shortest path found using A* on any discretized graph as illustrated in FIG.4A is not equivalent to an actual shortest path in a continuous environment as illustrated in FIG.4B. In FIG.4A and FIG.4B, Sstart and Sgoal generally represent start vertex and goal vertex of a search path and all cells other than those specifically indicated as blocked cells are unblocked cells. Subsequently, a technique which smoothens the path as it is being greedily evolved, thus reducing the gap (between the shortest path using square grid and continuous shorted path) extensively, was developed in the form of Theta* algorithm. Theta* is a variant of A* that does not constrain the path being evolved to stick to grid edges. The key difference between Theta* and A* is that Theta* allows the parent of a vertex to be any vertex, unlike A* where the parent must be a visible neighbor. To have such extended, transitive parental relation, Theta* updates the g-value (length of the shortest path from a start vertex to vertex s found so far) and parent of an unexpanded visible neighbor s' of vertex s by considering an alternative extension. To allow for any-angle paths, in each iteration, Theta* additionally considers the grandfatherly extension from parent(s) to neighbor s' in a straight line [cost = c(parent(s), s')], resulting in a new length of g(parent(s)) + c(parent(s),s') if s' has line-of-sight to parent(s). The idea behind considering the alternative path is that in case of Euclidean shortest path problems, the alternative path is never longer than previous default path, due to triangle inequality (for any triangle, the sum of the lengths of any two sides must be greater than or equal to the length of the remaining side), if s' has line-of-sight to parent(s). If line of sight is not present, then the extension in current iteration happens in the normal A* way, along the grid.
To reduce computational complexity, in an embodiment, the one or more processors 104 are configured to discretize, at step 202, a 3-Dimensional (3D) Euclidean navigation space of an aerial vehicle for tractability. A grid of a plurality of unit cells is imposed on the 3D Euclidean navigation space, wherein the grid may be either a patterned grid or an irregular grid. In a discrete 3D Euclidean navigation space with obstacles, it is known that the underlying set of grid points is not convex. Also, for spaces of dimension 3 and above, the path optimization problem is NP (Non-deterministic Polynomial) hard. Hence algorithms, typically inspired by shortest path algorithms in a convex domain, e.g. Dijkstra, have been researched for design for approximately optimal solutions/paths. The Theta* algorithm, which is a basic approximation algorithm improves upon the approximation error while using A*, by trading off minimally with computational complexity. Hence Theta* algorithm has been used in the present disclosure.
In accordance with the present disclosure, first a feasible space within the 3D (or 2D) Euclidean space is identified. The plurality of constraints described herein above are then applied to identify a subspace of the 3D (or 2D) Euclidean space in which the path maybe physically present as a union of navigable regions. More precisely, since the Euclidean space is discretized into a grid-based graph, some of the constraints may lead to a bigger feasible set that is a forest. For the remaining constraints, a greedy search is performed within the forest for optimal paths while simultaneously obeying the remaining constraints during greedy path formation via stepwise path augmentation.
In accordance with the present disclosure, the minimum separation constraint and the maximum separation constraint are two constraints that lead to direct pruning of the Euclidean space. In an embodiment, the one or more processors 104 are configured to identify, at step 204, a flight corridor in the 3-D Euclidean navigation space defined between the minimum separation constraint and the maximum separation constraint. FIG.5 illustrates a flight corridor identified in 3-Dimensional (3D) Euclidean navigation space of an aerial vehicle based on a minimum separation constraint and a maximum separation constraint in accordance with the present disclosure. The target under consideration for surveillance is a transmission line modeled as shown in FIG.5. It may be noted that imposition of the minimum separation constraint leads to creation of a half space on either side of the infrastructure (the transmission line modeled as the target under consideration for surveillance). Each of the half space may extend till infinity but does not intersect the infrastructure itself. Similarly, the imposition of the maximum separation constraint leads to creation of another half space on either side of the infrastructure. The half space arising from the maximum separation constraint not only extends in the opposite direction of the half space arising from the minimum separation constraint, but also intersects the infrastructure and does not extend till infinity. The method 200 of the present disclosure necessitates that the minimum separation constraint and the maximum separation constraint be obeyed simultaneously, thereby identifying the flight corridor generated by intersection of the two half spaces described herein above. In a 2D scenario, the flight corridor lies on either side of the target under consideration which in a 3D scenario, the flight corridor is a cylindrical annulus around the target under consideration.
In accordance with the present disclosure, the one or more processors 104 are configured to identify, at step 206, a current node, a grandparent node and a parent node associated with the current node, in a partial path generated offline for the aerial vehicle in the flight corridor identified at step 204. FIG.6 illustrates node nomenclature for a shortest path algorithm, in accordance with an embodiment of the present disclosure. In an embodiment, the one or more processors 104 are configured to iteratively, at step 208, identify a neighbor node for the current node to augment the partial path, for surveillance of the target under consideration. The step 208 involves several sub-steps as explained hereinafter.
In an embodiment, the one or more processors 104 are configured to, at step 208a, identify at least one potential neighbor node of the current node satisfying a line of sight condition with the parent node or satisfying a collinear condition with the current node and the parent node. If a line of sight exists, then using the triangle inequality the partial path is augmented offline, up to the at least one potential neighbor node by turning at a location corresponding to the parent node.
In the event that the parent node, the current node and the potential neighbor node are non-collinear, the one or more processors 104 are configured to, at step 208b, evaluate the minimum route leg length constraint between the parent node and the current node to identify one of the at least one potential neighbor node as the neighbor node for augmenting the partial path. The minimum route leg length would have already been performed between the grandparent node and parent node, by the time the partial path augmentation reaches the current node. Therefore, at the current node, while choosing a potential neighbor node to augment the partial path in a best-first way, minimum route leg length constraint check is carried out involving parent node, current node and the potential neighbor node only. Each of the potential neighbor nodes may be evaluated for the minimum route leg length constraint until one of the potential neighbor nodes satisfies the minimum route leg length constraint for augmenting the partial path.
In the event that one of the minimum route leg length constraint, the line of sight condition or the collinear condition is satisfied by the at least one potential neighbor node, the one or more processors 104 are configured to, at step 208c, further evaluate the maximum turn angle constraint consistency for the at least one potential neighbor node (of a direction set pertaining to the at least one potential neighbor node with the parent node). The maximum turn angle constraint consistency is evaluated first with respect to the direction set pertaining to the grandparent node and further evaluated with respect to the direction set pertaining to the parent node in the event that the evaluation with respect to the grandparent node fails, to identify another one of the at least one potential neighbor node as the neighbor node for augmenting the partial path.
As stated herein above in the present disclosure, the applicant has explained the maximum turn angle constraint in a previous patent application no. 201721001481 filed on 13 January, 2017 at the Indian Patent Office, parts of which are re-produced herewith for explanation. In an embodiment, the maximum turn angle constraint for the at least one potential neighbor node is evaluated with respect to the grandparent node by checking if the angle subtended by (a) a line between the grandparent node and the parent node and b) a line between the parent node and the potential neighbor node is within a pre-determined maximum turning angle of the aerial vehicle identifying one of the at least one potential neighbor node as the neighbor node. If the turn angle is 0 degree, then the constraint is trivially true. If the evaluation with respect to the grandparent node fails, the maximum turn angle constraint for the at least one potential neighbor node is then evaluated with respect to the parent node by checking if the angle subtended by (a) a line between the parent node and the current node and b) a line between the current node and the potential neighbor node is within the pre-determined maximum turning angle of the aerial vehicle. Once again, if the turn angle is 0 degree, then the constraint is trivially true. If in both cases explained herein above, the potential neighbor node fails the maximum turn angle constraint, and is not found suitable to qualify as a neighbor node for augmenting the path, then the neighbor node under consideration may be dropped from consideration and another neighbor node of the current node may be evaluated for compatible turn angle constrained path augmentation.
In the event that either the maximum turn angle constraint consistency or the minimum route leg length constraint fails for each of the at least one potential neighbor nodes, the one or more processors 104 are configured to, at step 208d, backtrack to at least one prior node along the augmented partial path until a previous iteration. Three scenarios of backtracking include (a) when the maximum turn angle constraint consistency fails for each of the at least one potential neighbor node using the triangle inequality to augment the partial path up to the at least one potential neighbor node by turning at a location corresponding to the parent node (b) when the maximum turn angle constraint consistency fails for each of the at least one potential neighbor node not using the triangle inequality to augment the partial path up to the at least one potential neighbor node by turning at a location corresponding to the current node and (c) when the minimum route leg length constraint fails for each of the at least one potential neighbor node not using the triangle inequality to augment the partial path between the parent node and the current node. In an embodiment, the one or more processors 104 are configured to, at step 208e, identify a backtracked node from the at least one prior node on the backtracked path as the current node for augmenting the partial path.
The present disclosure, particularly addresses continued transmission of surveillance data in the presence of coverage holes. Accordingly, in an embodiment, the step of identifying a neighbor node for the current node to augment the partial path further comprises evaluating, at step 208f, the storage constraint for each of the at least one potential neighbor node in the event that a coverage hole is encountered along the augmented partial path. The storage constraint evaluation, in accordance with the present disclosure, is based on potential augmented partial paths within the coverage hole having identical entry point into the coverage hole. Once a partial path arrives at a grid node on the boundary, its extension within coverage hole has to be strictly within the (storage) upper bounded length. The partial path evolves inside the coverage hole in the normal best-first way, exploring alternative internal path segments iteratively (dropping part or whole of path segments till previous iteration), till a best possible segment for augmenting the partial path is found.
As in the case of failure of the maximum turn angle constraint consistency or the minimum route leg length, in the event of failure of the storage constraint consistency for each of the at least one potential neighbor nodes also, the one or more processors 104, at step 208g, backtracks to least one prior node along the augmented partial path until a previous iteration. The method 200 also ensures the storage constraint or the upper bounded length constraint is not imposed at the end or around the time when the head of the evolving path is at exit point on the coverage hole boundary. Imposing the constraint at the beginning is done because, in case of upper bounded length violation, the path would have to backtrack all the way to the coverage hole entry point to find another segment for augmenting. To avoid backtracking all the way, the method 200 evaluates at each current node within the coverage hole to check whether the further path augmentation may lead to violation of the storage constraint. For the current node, the upper bounded length constraint cannot be breached; else the augmented partial path would not have reached till the current node. Accordingly, evaluation of the storage constraint is performed for each of the at least one potential neighbors of the current node. Only if augmentation along any of the potential neighbor nodes is not possible, does the method 200 initiate backtracking of the path.
To estimate how much distance from the current node must the path backtrack, how minimally far the current node is from each of the finite boundary points of the coverage hole is computed. A cumulative distance of the current node from the entry point within the coverage hole is also computed. A potential backtracked node is identified in the augmented partial path at a distance indicative of the overflow based on the pre-defined upper bounded length, the computed shortest distance of the current node from the finite boundary points and the computed cumulative distance. Then, along the path evolved, the augmented partial path traverses back by the distance indicative of the overflow, appropriately rounded off to the nearest integer. Since such point need not lie on the grid corners, the nearest grid corner along the path of evolution so far is identified as the potential backtracked node. FIG.7 illustrates backtracking to a prior node within a coverage hole, in accordance with an embodiment of the present disclosure. Segments AB, CD and DE represent paths (one cell at a time) that the method 200 may follow ideally. Segments BF, FC, CG represent paths that the method 200 may follow in accordance with the present disclosure. Segment GH represents a computed distance of the current node G from the closest boundary point H of the coverage hole. In the event that the sum of the cumulative distance of the current node G from the entry point B and the distance GH exceeds the pre-defined upper bounded length, L, backtracking is initiated. The dashed segment GC and CF represent backtracking from the current node G to a potential backtracked node F by a distance that is approximately equal to the distance {(BG + GH) – L}. D represents an actual backtracked location that is a grid corner closest to the potential backtracked node F.
The backtracking step of the method 200 entails approximation errors. However, the more important advantage of pruning the search space in near-maximal chunks, and further in predictive fashion cannot be ignored. Also, if backtracking is performed partially but not fully, then at some point, after exploring the search space from the backtracked node, further backtracking may happen. Such incremental augmentation enables finding a shortest path segment if it exists, in a reasonably fast manner.
There may be some degenerate scenarios wherein, the path augmentation may not proceed as described herein above. In such scenarios, ease of designing path augmentation may be traded off with some degree of optimization error. For instance, in one scenario, it may happen that after finding one good path segment about to extend out of a coverage hole, there exist better path segments passing through the same coverage hole, given the same entry point. It is known that in best-first search, the next extension is not always from the current (head) node of the path evolved so far. Towards such scenario, whenever a path is entering into a coverage hole, an exhaustive exploration is performed within the entire hole, starting from same entry point. Even though this increases computational complexity a bit initially, it avoids late re-exploration of the coverage hole in the specific scenario when the head of the currently evolved path has grown beyond the coverage hole, and then due to best-first nature of the algorithm, a node from inside the coverage hole being considered pops up from the heap in the next iteration. If such case were allowed to happen, then some amount of path planning beyond the coverage hole gets discarded. To implement such exploration, an “inner” open list is created, having the coverage hole entry point and its descendants which are inner nodes. While expanding using the open list (having the main open list parked), if the path head reaches a boundary node of that coverage hole, path expansion is not allowed to go out of the coverage hole until all other possible exit points, given a fixed entry point of the planned path into that specific coverage hole, are discovered. At the end, only possible exit points remain on the inner open list, and they are merged into the main open list, so that the “best” possible exit option is naturally picked up in the next iteration of (overall) path expansion.
In another scenario, it may happen that a line-of-sight based merging between a neighbor of the current node that is inside a coverage hole, happens to be with parent of the current node that is outside the coverage hole. Such merging may lead to added design complexity, since the entry point of the augmented path into the coverage hole shifts. In turn, the calculated cumulative length so far within coverage hole that is to be checked against upper bound every iteration, becomes incorrect. By working with a separate open list while exploring inside a coverage hole, having only inner or boundary nodes in it, design complexity gets avoided.
Alternatively, as a reverse scenario, it may happen that a line-of-sight based merging between a neighbor of the current node that is outside a coverage hole, happens to be with parent of the current node that is inside the coverage hole. Much in the same way as the previous scenario, the cumulative distance calculations become invalid since the exit point shifts. In accordance with the present disclosure, the exit point of the hole as a boundary point is forced to become a parent node, thus disallowing merging of the above nature. This also helps in thwarting the possibility of a line-of-sight-based remote merging between two exterior nodes of an evolving path that will intersect a coverage hole that has already been fully explored. Such scenario especially arises when there are multiple holes and multiple obstacles, as may be most practically the case.
Such design of forcing entry and exit nodes of an augmenting path to be a forced parent node works even in the scenario when an augmenting path inside a coverage hole just touches the hole boundary, does not go out and immediately reenters into the same hole. Such consideration keeps the method 200 fail proof and less complex.
As a final scenario, while doing the path planning, the minimum route leg length constraint needs to be checked only when the parent, current and neighbor are non-collinear. If they are collinear, the path was augmented up to that point after satisfying the minimum route leg length constraint and addition of one more step in the same direction will not cause failure of the constraint. Thus a lot of duplicated checking in the algorithm is avoided.
Thus in accordance with the present disclosure, systems and methods described herein above impose a plurality of constraints to obtain a shortest path that can ensure continuous transmission of surveillance data. The method 200 further comprises storing data associated with the surveillance of the target under consideration, onboard, at step 210, in the event that the storage constraint fails. This averts overflow of the onboard storage device by minimizing onboard storage to an extent possible and ensuring shortest paths through the coverage hole to ensure continuity of transmission.
The written description describes the subject matter herein to enable any person skilled in the art to make and use the embodiments of the present disclosure. The scope of the subject matter embodiments defined here may include other modifications that occur to those skilled in the art. Such other modifications are intended to be within the scope if they have similar elements that do not differ from the literal language of the claims or if they include equivalent elements with insubstantial differences from the literal language.
The scope of the subject matter embodiments defined here may include other modifications that occur to those skilled in the art. Such other modifications are intended to be within the scope if they have similar elements that do not differ from the literal language of the claims or if they include equivalent elements with insubstantial differences from the literal language.
It is, however to be understood that the scope of the protection is extended to such a program and in addition to a computer-readable means having a message therein; such computer-readable storage means contain program-code means for implementation of one or more steps of the method, when the program runs on a server or mobile device or any suitable programmable device. The hardware device can be any kind of device which can be programmed including e.g. any kind of computer like a server or a personal computer, or the like, or any combination thereof. The device may also include means which could be e.g. hardware means like e.g. an application-specific integrated circuit (ASIC), a field-programmable gate array (FPGA), or a combination of hardware and software means, e.g. an ASIC and an FPGA, or at least one microprocessor and at least one memory with software modules located therein. Thus, the means can include both hardware means and software means. The method embodiments described herein could be implemented in hardware and software. The device may also include software means. Alternatively, the embodiments of the present disclosure may be implemented on different hardware devices, e.g. using a plurality of CPUs.
The embodiments herein can comprise hardware and software elements. The embodiments that are implemented in software include but are not limited to, firmware, resident software, microcode, etc. The functions performed by various modules comprising the system of the present disclosure and described herein may be implemented in other modules or combinations of other modules. For the purposes of this description, a computer-usable or computer readable medium can be any apparatus that can comprise, store, communicate, propagate, or transport the program for use by or in connection with the instruction execution system, apparatus, or device. The various modules described herein may be implemented as software and/or hardware modules and may be stored in any type of non-transitory computer readable medium or other storage device. Some non-limiting examples of non-transitory computer-readable media include CDs, DVDs, BLU-RAY, flash memory, and hard disk drives.
Further, although process steps, method steps, techniques or the like may be described in a sequential order, such processes, methods and techniques may be configured to work in alternate orders. In other words, any sequence or order of steps that may be described does not necessarily indicate a requirement that the steps be performed in that order. The steps of processes described herein may be performed in any order practical. Further, some steps may be performed simultaneously.
The preceding description has been presented with reference to various embodiments. Persons having ordinary skill in the art and technology to which this application pertains will appreciate that alterations and changes in the described structures and methods of operation can be practiced without meaningfully departing from the principle, spirit and scope.