Distributed Motion Planning and Control of Autonomous Ground and Aerial Vehicles

Abstract

An autonomous ground vehicle (AGV) carrying one or multiple unmanned aerial vehicles (UAVs) to perform one or multiple tasks necessitating visiting one or multiple target locations is controlled by determining a reachable set defining a region of space including a target location for performing the task and a difference between a launch time span for launching the UAV and a recovery time span recovering the UAV. The AGV motion trajectory prescribes the AGV to be in a launch location within the reachable set at a launch time within the launch time span and in a recovery location within the reachable set at a recovery time within the recovery time span subject to a constraint on the difference between the launch time span and the recovery time span.

Claims

1. A method for controlling an autonomous ground vehicle (AGV) carrying one or multiple unmanned aerial vehicles (UAVs) to perform one or multiple tasks necessitating visiting one or multiple target locations, wherein the method uses a processor coupled with stored instructions implementing the method, wherein the instructions, when executed by the processor carry out steps of the method, comprising: collecting energy budgets for each of the one or multiple tasks to be performed by each of the one or multiple UAVs; determining, for each of the tasks based on an energy budget collected for a task and an energy model of a UAV assigned to the task, a reachable set defining a region of space including a target location for performing the task that enables the UAV located in the reachable set to reach the target location, spent a predetermined energy for performing the task and exit the reachable set while staying within the energy budget and operating within a safe envelope of flight conditions; determining, based on the energy model of the UAV, a difference between a launch time span and a recovery time span of the UAV based on dimensions of the reachable set and time allocated for the performance of the task corresponding to the energy predetermined for the task; determining an AGV motion trajectory as a function of time and space prescribing the AGV to be in a launch location within the reachable set at a launch time within the launch time span and in a recovery location within the reachable set at a recovery time within the recovery time span subject to constraints including a constraint on the difference between the launch time span and the recovery time span; and controlling the AGV according to the AGV motion trajectory while commanding the UAV to perform the task upon reaching the launch location at the launch time and collecting the UAV in the recovery location at the recovery time.

2. The method of claim 1, wherein the reachable set is an intersection of a Lyapunov stability set defined by a first Lyapunov function and a Lyapunov energy set defined by a second Lyapunov function, wherein the Lyapunov stability set is determined for a feedback controller of the UAV and flight constraints defining the safe envelope of flight conditions such that the UAV located within the Lyapunov stability set under the control of the feedback controller reaches an equilibrium for a sublevel set of the first Lyapunov function while satisfying the flight constraints, and wherein the Lyapunov energy set is determined for a sublevel set of the second Lyapunov function describes energy usage of the UAV controlled by the feedback controller according to the energy model of the UAV, wherein a value of the sublevel set is determined by the energy budget.

3. The method of claim 2, wherein the plurality of tasks includes a first task at a first target location and a second task at a second target location, wherein the Lyapunov stability sets for the first and second tasks are determined based on the same values of the sublevel set of the first Lyapunov function and different values of the sublevel set of the second Lyapunov function.

4. The method of claim 3, wherein the Lyapunov stability set for the first task is determined for the equilibrium aligned with the first target location, and wherein the Lyapunov stability set for the second task is determined for the equilibrium aligned with the second target location.

5. The method of claim 4, wherein the processor is operatively connected to a database storing the memory is configured to access different sublevel sets of the first Lyapunov function and different sublevel sets of the second Lyapunov function, further comprising: selecting the sublevel set of the first Lyapunov function allowing stability satisfying the flight constraints for operating the UAV under current weather conditions; and selecting the sublevel set of the second Lyapunov function in response to collecting the energy budget.

6. The method of claim 1, further comprising: assigning tasks from the plurality of tasks to the UAV; and determining the energy budget for performing the task by the UAV by dividing an energy capacity of the UAV by a number of the assigned tasks.

7. The method of claim 1, further comprising: determining the energy budget for performing the task by the UAV based on a predetermined value of an energy capacity of the UAV; and controlling the AGV to charge the UAV between the recovery time of the task and the launch time of subsequent tasks till the energy capacity of the UAV reaches the predetermined value.

8. The method of claim 1, further comprising: determining a current level of an energy capacity of the UAV at the recovery time after performing the task; comparing the current level of the energy capacity with an energy budget allocated for performing a subsequent task and a distance between the recovery location of the task and the launch location of the subsequent task indicative of charging time for recharging the AUV before performing the subsequent task; and updating the energy budget and the reachable set of the subsequent task based on the comparison.

9. The method of claim 1, wherein the UAV is configured to return to the recovery location when a current level of energy remaining at the UAV is less than a level allocated by the energy budget for a recovery path from the target location to the recovery location.

10. The method of claim 9, wherein the UAV is configured to return to the recovery location when a remaining time till the recovery time is less than a flying time allocated for flying along the recovery path.

11. The method of claim 1, further comprising: determining the AGV motion trajectory by solving an optimization problem minimizing a cost function of time of AGV motion and energy used during the AGV motion subject to the constraints, a cost of operation of the AGV, and a cost of operation of the UAV, to produce the AGV motion trajectory passing through the reachable sets determined for each of the plurality of tasks.

12. The method of claim 11, wherein the constraints include a motion model of the AGV, constraints on the motion of the AGV, initial conditions and terminal conditions for the AGV, constraints on obstacle avoidance of the AGV, and constraints on the AGV position to be within the region where the UAV can launch and return with available UAV energy and while satisfying UAV constraints, at times where the UAV can reach the AGV position.

13. The method of claim 12, wherein the energy budget is optimized within a range that modifies the constraints on the AGV position to be within the in region where the UAV can return at times where the UAV can reach the AGV position.

14. The method of claim 2, wherein the UAV motion between the launch and target locations and between the target and recovery locations is controlled according to the feedback controller of the UAV that determines the Laypunov stability set associated with constructing the first Lyapunov function.

15. The method of claim 14, wherein the first Lyapunov function is computed together with the feedback controller by solving a convex optimization problem with exponentially stabilizing Lyapunov linear matrix inequality constructed from a motion model of the UAV.

16. The method of claim 15, wherein the exponentially stabilizing linear matrix inequality is solved by an exponentially stabilizing semidefinite program that optimizes the size of the Lyapunov stability set where the constraints on the motion of the UAV are satisfied

17. The method of claim 15, wherein the matrix inequality constraints impose that the first Lyapunov function achieves exponential stability and provides time bound to reach the position to start the task from the AGV, and the time bound to reach AGV landing range from the location of the target of the task execution.

18. The method of claim 15, wherein the second Lyapunov function is computed by solving an autonomous system Lyapunov matrix equation constructed from a motion model of the UAV and the feedback controller obtained together with the first Lyapunov function.

19. An autonomous ground vehicle (AGV) configured for carrying one or multiple unmanned aerial vehicles (UAVs) to perform one or multiple tasks necessitating visiting one or multiple target locations, wherein the AGV includes a processor coupled with stored instructions, wherein the instructions, when executed by the processor, cause the processor to: collect energy budgets for each of the one or multiple tasks to be performed by each of the one or multiple UAVs; determine, for each of the tasks based on an energy budget collected for a task and an energy model of a UAV assigned to the task, a reachable set defining a region of space including a target location for performing the task that enables the UAV located in the reachable set to reach the target location, spent a predetermined energy for performing the task and exit the reachable set while staying within the energy budget and operating within a safe envelope of flight conditions; determine, based on the energy model of the UAV, a difference between a launch time and a recovery time of the UAV based on dimensions of the reachable set and time allocated for the performance of the task corresponding to the energy predetermined for the task; determine an AGV motion trajectory as a function of time and space prescribing the AGV to be in a launch location within the reachable set at the launch time and in a recovery location within the reachable set at the recovery time subject to a constraint on the difference between the launch time and the recovery time; and control the AGV according to the AGV motion trajectory while commanding the UAV to perform the task upon reaching the launch location at the launch time and collecting the UAV in the recovery location at the recovery time.

20. A non-transitory computer-readable storage medium and embodied thereon a program executable by a processor performing a method for controlling an autonomous ground vehicle (AGV) carrying one or multiple unmanned aerial vehicles (UAVs) to perform one or multiple tasks necessitating visiting one or multiple target locations, the method comprising: collecting energy budgets for each of the one or multiple tasks to be performed by each of the one or multiple UAVs; determining, for each of the tasks based on an energy budget collected for a task and an energy model of a UAV assigned to the task, a reachable set defining a region of space including a target location for performing the task that enables the UAV located in the reachable set to reach the target location, spent a predetermined energy for performing the task and exit the reachable set while staying within the energy budget and operating within a safe envelope of flight conditions; determining, based on the energy model of the UAV, a difference between a launch time and a recovery time of the UAV based on dimensions of the reachable set and time allocated for the performance of the task corresponding to the energy predetermined for the task; determining an AGV motion trajectory as a function of time and space prescribing the AGV to be in a launch location within the reachable set at the launch time and in a recovery location within the reachable set at the recovery time subject to a constraint on the difference between the launch time and the recovery time; and controlling the AGV according to the AGV motion trajectory while commanding the UAV to perform the task upon reaching the launch location at the launch time and collecting the UAV in the recovery location at the recovery time.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0017] Having thus described example embodiments of the disclosure in general terms, reference will now be made to the accompanying drawings, which are not necessarily drawn to scale, and wherein:

[0018] FIG. 1 shows an exemplar schematic of controlling an AGV carrying one or multiple UAVs to perform one or multiple tasks necessitating visiting one or multiple target locations according to some embodiments.

[0019] FIG. 2A shows a schematic of a control system implemented on the AGV for controlling a fleet of Unmanned Aerial Vehicles (UAVs), in accordance with an example embodiment.

[0020] FIG. 2B illustrates a block diagram of an AGV including a mobile terminal, in accordance with an example embodiment.

[0021] FIGS. 3A-3B show schematics of exemplar implementations of UAV and UAV used for performing different tasks, such as delivery services and monitoring tasks, in accordance with different embodiments.

[0022] FIG. 4 shows a pseudo-code of a joint motion control problem for controlling hybrid robots of different dynamics addressed by different embodiments.

[0023] FIG. 5 shows a schematic of decoupling the joint motion planning problem into an AGV motion planning and UAV motion planning according to some embodiments.

[0024] FIG. 6A shows a block diagram of method for controlling an autonomous ground vehicle (AGV) carrying one or multiple unmanned aerial vehicles (UAVs) to perform one or multiple tasks necessitating visiting one or multiple target locations according to some embodiments.

[0025] FIG. 6B shows a schematic of the architecture of a decoupled motion planning system where the motion planners of UAVs, provide the reachable regions to an AGV motion planner.

[0026] FIG. 7A shows a schematic illustrating the dependency between the energy budget, energy model, and the task to be performed, with the difference between launch and recovery time spans employed by some embodiments.

[0027] FIG. 7B shows a schematic of determining different reachable sets of launch and recovery operations according to some embodiments.

[0028] FIG. 8 shows a schematic illustrating a method for determining a reachable set as an intersection of a Lyapunov stability set defined by a first Lyapunov function and a Lyapunov energy set, or defined by a second Lyapunov function, according to some embodiments.

[0029] FIG. 9 shows a schematic illustrating the additional flexibility of energy-based reachable sets according to some embodiments.

[0030] FIG. 10 shows a schematic of a method for determining a reachable set under the special assumption of a linear control method for the linear motion of the UAVs according to some embodiments.

[0031] FIG. 11 shows a schematic of time calculation for launch and recovery operations according to some embodiments.

[0032] FIGS. 12A and 12B show schematics of computation of launch and return commands and trajectories based on reachable regions according to some embodiments.

[0033] FIGS. 13A and 13B show schematics of allocating energy budget for performing different tasks by different UAVs according to different embodiments.

[0034] FIG. 13B shows a schematic of an embodiment allowing for recharging the UAV between the performance of the tasks.

[0035] FIG. 13C shows a flow chart of a method for determining energy budgets dynamically based on the actual performance of the tasks according to some embodiments.

[0036] FIG. 14 shows a pseudo-code of an exemplar optimization method employed by some embodiment.

[0037] FIG. 15 shows a block diagram of a method for an iterative estimation of the AGV and UAV initial motion trajectories according to some embodiments.

[0038] FIG. 16 illustrates a block diagram of a controller for the exemplar UAV according to an exemplary embodiment.

[0039] FIG. 17 illustrates a schematic of a computing device for implementing the system and joint planning methods of the present disclosure, in accordance with an example embodiment.

DETAILED DESCRIPTION

Problem Overview

[0040] It is an object of some embodiments to control an autonomous ground vehicle (AGV) carrying one or multiple unmanned aerial vehicles (UAVs) to perform one or multiple tasks necessitating visiting one or multiple target locations over an uncertain duration by one or multiple UAVs. AGVs can include different types of vehicles configured for autonomous driving and suitable for carrying the UAVs from one location to another. Examples of AGVs include various unmanned vehicles, such as robots and rovers, a ground vehicle, as well as autonomous vehicles capable of carrying passengers in addition to drones. Examples of UAVs include various aerial drones in various shapes and sizes, both fixed and rotating wings, and designed for different purposes, such as consumer drones, [0041] professional drones, industrial drones, and agriculture drones.

[0042] FIG. 1 shows an exemplar schematic of controlling an AGV carrying one or multiple UAVs to perform one or multiple tasks necessitating visiting one or multiple target locations according to some embodiments. An AGV 110 is controlled according to a motion trajectory 115 defining different locations 112 and 114 of the AGV 110 at different instances of time. In this example, the motion trajectory 115 leads the vehicle 110 in proximity to the target locations, depicted as stars, such as stars 141 and 142, till the final location 120.

[0043] The motion trajectory 115 goes around non-traversable terrain and boundaries, such as mountains 130, 135, and river 137. When the AGV 110 is in proximity to the target locations, the AGV commands UAVs, e.g., UAV 125 and/or 126, to visit target locations to perform a task. The AGV can continue its motion while the AUV performs the task. For example, a UAV 126 can travel to a target location 143 from a vehicle at launch location 112 and return from the target location 143 over a trajectory 155 to the AGV at a recovery location 114, which is different from the launch location 112. In such a manner, the joint performance of AGV and UAV can be improved, but the motions of the AGV and UAV should be planned jointly.

[0044] FIG. 2A shows a schematic of a control system 201a implemented on the AGV 110 for controlling a fleet of Unmanned Aerial Vehicles (UAVs), in accordance with an example embodiment. As shown in FIG. 2A, the control system 201a is communicatively coupled to a fleet of UAVs 213al via a communication network 211a. The fleet of UAVs 213al includes a plurality of drones, i.e., a UAV 213a, a UAV 213b, a UAV 213c, and a UAV 213d. The fleet of UAVs 213al may be stationed at platform 213e arranged on the AGV 110. The system 201a includes a processor 203a and a memory 205a. The system 210a can also include or be connected to a database 207a, and a user interface 209a. Memory 205a includes stored instructions 205aa implementing the joined control method. The processor 203a is coupled with the stored instructions implementing the method, wherein the instructions, when executed by the processor carry out steps of the joined control method.

[0045] Various components of the control system 201a may be coupled directly or indirectly to the communication network 211a. The communication network 211a may be wired, wireless, or any combination of wired and wireless communication networks, such as cellular, Wi-Fi, internet, local area networks, or the like. In some embodiments, the communication network 211a may include one or more networks such as a data network, a wireless network, a telephony network, or any combination thereof. It is contemplated that the data network may be any local area network (LAN), metropolitan area network (MAN), wide area network (WAN), a public data network (e.g., the Internet), short range wireless network, or any other suitable packet-switched network, such as a commercially owned, proprietary packet-switched network, e.g., a proprietary cable or fiber-optic network, and the like, or any combination thereof. In addition, the wireless network may be, for example, a cellular network and may employ various technologies including enhanced data rates for global evolution (EDGE), general packet radio service (GPRS), global system for mobile communications (GSM), Internet protocol multimedia subsystem (IMS), universal mobile telecommunications system (UMTS), etc., as well as any other suitable wireless medium, e.g., worldwide interoperability for microwave access (WiMAX), Long Term Evolution (LTE) networks (for e.g. LTE-Advanced Pro), 5G New Radio networks, International Mobile Telecommunications (ITU-IMT) 2020 networks, code division multiple access (CDMA), wideband code division multiple access (WCDMA), wireless fidelity (Wi-Fi), wireless LAN (WLAN), Bluetooth, Internet Protocol (IP) data casting, satellite, mobile ad-hoc network (MANET), and the like, or any combination thereof. The components of the control system 201a may be further broken down into more than one component and/or combined together in any suitable arrangement. Further, one or more components may be rearranged, changed, added, and/or removed.

[0046] The system 201a includes suitable logic, circuitry, and interfaces that may be configured to control the one or more UAVs of the fleet of UAVs 213al to perform the one or more missions efficiently. In some embodiments, the fleet of UAVs 213al may be stationed at the initial terminal 213e. Further, at least one of the UAV 213a, the UAV 213b, the UAV 213c, and the UAV 213d may be used to perform the one or more missions efficiently. In some embodiments, the system 201a may be embodied as a chip or chip set. In other words, the system 201a may comprise one or more physical packages (such as chips) that includes materials, components and/or wires on a structural assembly (such as, a baseboard).

[0047] The memory 205a of the system 201a may include one or more modules related to, but not limited to, related to, but not limited to, geocoding, routing (multimodal, intermodal, and unimodal), clustering algorithms, machine learning in location-based solutions, natural language processing algorithms, and artificial intelligence algorithms. Data for one or more modules of the memory 205a may be collected using a plurality of technologies including, but not limited to drones, sensors, connected cars, cameras, interfaces, probes, and chipsets.

[0048] In some embodiments, memory 205a may be non-transitory and may include, for example, one or more volatile and/or non-volatile memories. In other words, for example, the memory 205a may be an electronic storage device (for example, a computer-readable storage medium) comprising gates configured to store data (for example, bits) that may be retrievable by a machine (for example, a computing device like the processor 203a). The Memory 205a may be configured to store information, data, content, applications, instructions, or the like, to enable the apparatus to carry out various functions in accordance with an example embodiment of the present invention. For example, the memory 205a may be configured to buffer input data for processing by the processor 203a. The memory 205a may be configured to store instructions for execution by the processor 203a. As such, whether configured by hardware or software methods, or by a combination thereof, the processor 203a may represent an entity (for example, physically embodied in circuitry) capable of performing operations according to an embodiment of the present invention while configured accordingly. Thus, for example, when processor 203a is embodied as an ASIC, FPGA, or the like, the processor 203a may be specifically configured hardware for conducting the operations described herein. Alternatively, as another example, when processor 203a is embodied as an executor of software instructions, the instructions may specifically configure processor 203a to perform the algorithms and/or operations described herein when the instructions are executed. However, in some cases, the processor 203a may be a processor-specific device (for example, a mobile terminal or a fixed computing device) configured to employ an embodiment of the present invention by further configuration of the processor 203a by instructions for performing the algorithms and/or operations described herein. The Processor 203a may include, among other things, a clock, an arithmetic logic unit (ALU), and logic gates configured to support the operation of the processor 203a.

[0049] In some embodiments, system 201a includes processor 203a for conducting processing functions associated with system 201a and database 207a for storing and retrieving data. In an embodiment, system 201a may comprise one or more processors configured to process requests received from system 201a. Further, in some embodiments, the database 207a comprises suitable logic, circuitry, and interfaces that may be configured to store the data associated with one or more participants of one or more missions.

[0050] In some implementations, the AGV 110 can be implemented as a mobile terminal configured to carry and charge the UAV 213al. Due to the length of the mission and limited charge available to UAVs, some UAVs may be unfeasible to perform the specific mission. However, the AGV 110 can be implemented as a mobile terminal and can transform an unfeasible UAV, i.e., unfeasible for a task, into a feasible UAV capable of carrying the mission.

[0051] FIG. 2B illustrates a block diagram 200b of an AGV including a mobile terminal 201b, in accordance with an example embodiment. As shown in FIG. 2B, the mobile terminal 201b includes a landing pad 205ab, a landing pad 205bb, a refilling mechanism 207b, a supply unit 209b, a processor 211b, a communication module 213b, and a refilling module 215b. The mobile terminal 201b is mounted on a vehicle platform 203b such as a truck that may be operated by a driver or autonomously by a ground vehicle controller. The vehicle platform 203b may include one or more sensors. The sensors include, but are not limited to geolocation sensors, light sensors, proximity sensors, image sensors, and the like. In some embodiments, the processor 211b is further configured to determine a reduced amount of fuel for each UAV of the fleet of UAVs 213al based on the joint motion optimization.

[0052] Further, based on the determined reduced amount of fuel, the processor 211b is further configured to transform a non-feasible UAV of the fleet of UAVs into a feasible UAV to perform the mission. Further, in some embodiments, the processor 211b is further configured to transform the UAV 27 by changing the location of the mobile terminal 201b. In one embodiment, the processor is configured to recover the UAV on the landing pad 205ab of the mobile terminal 201b. In one embodiment, the processor 211b is configured to transform the non-feasible UAV into a feasible UAV by refilling fuel using the refilling mechanism 207b. Further, the refilling mechanism 207b is associated with the refilling module 215b and the supply unit 209b.

[0053] The refilling mechanism 207b is integrated into the mobile terminal 201b and is coupled with each landing pad of the mobile terminal 201b via the communication module 213b. The refiling mechanism 207b is configured to perform the refiling of resources for one or more missions associated with one or more UAVs. The resources may include, but are not limited to: fuel, energy, consumables, fluids, and materials. The refilling mechanism 207b may include resource containers, flow control valves, resource compatibility sensors, a pumping mechanism, a recharging mechanism, a pressure monitoring system, flow rates sensors, safety interlocks, a leak detection system, and a refiling control panel.

[0054] Further, the supply unit 209b is connected with the refilling mechanism 207b via the refilling module 215b. The refilling module 215b is configured to receive a resource request from the refilling mechanism 207b. Further, based on the resource request, the supply unit 209b is configured to provide the resources to the refilling mechanism 207b. Additionally, the supply unit 209b is further configured to store, distribute, control, and monitor the resources for one or more missions.

[0055] Referring back to FIG. 2A, in some embodiments, the one or more UAVs of the fleet of UAVs 213al include one or more sensors, user equipment, and/or a communication interface (not shown in FIG. 2A). Additional, fewer, or different components may be provided. For example, a proxy server, a name server, a map server, a cache server or cache network, a router, a switch or intelligent switch, an additional database, additional computers or workstations, administrative components, such as an administrative workstation, a gateway device, a backbone, ports, network connections, and network interfaces may be provided. While the components in FIG. 2A are shown as separate from one another, one or more of these components may be combined. In this regard, system 201a may be communicatively coupled to the components shown in FIG. 2A to carry out the desired operations and wherever required modifications may be possible within the scope of the present disclosure.

[0056] Referring back to FIG. 2A, in some embodiments, the control system 211a is located in the vehicle 110, such that the link 211b is a local communication. In other embodiments the control system 211a is located remotely with respect to the vehicle 110, such that the link 211b is a communication network as 211a.

[0057] FIGS. 3A-3B show schematics of exemplar implementations of UAV 300 and UAV 310 used for performing different tasks, such as delivery services and monitoring tasks, in accordance with different embodiments. The UAV 300 corresponds to one of UAVs of the fleet of UAVs 213al, e.g., the UAV 213a. As shown in FIG. 3A, the UAV 300 comprises a rotor blade 301a, a rotor blade 301b, a rotor blade 301c, a rotor blade 301d, and a mechanical claw 303 for carrying a package 305.

[0058] As shown in FIG. 3B, in various implementations the UAV is equipped with sensors for performing monitoring tasks. For example, the UAV 310 maybe equipped with localization and flying sensors, monitoring sensors 320, 325, and/or guidance system 330.

[0059] Referring back to FIG. 3A, in some embodiments, the UAV 300 may be a single-rotor UAV that comprises a single rotor blade. In some embodiments, the UAV 300 may be a Tri copter that comprises three rotor blades. In some embodiments, the UAV 300 is a quadcopter that comprises four rotor blades. In some embodiments, the UAV 300 is a hex copter that comprises six rotor blades. In some embodiments, the UAV 300 is an octocopter that comprises eight rotor blades. In some embodiments, the UAV 300 having more than one rotor blade may be referred to as multi-rotor UAV. Further, in some embodiments, the UAV 300 is a fixed-wing UAV that comprises a fixed wing. In some embodiments, the UAV 300 is a fixed-wing hybrid vertical take-off landing (VTOL) UAV that is a hybrid of the fixed-wing UAV and VTOL aircrafts. In some embodiments, the one or more rotors may be referred to as one or more propellers.

[0060] Further, the UAV 300 may include one or more means for carrying the package 305. One or more means include, but are not limited to, a vacuum mechanism, magnetic mechanism, electro-magnetic mechanism, or suction cup fastening mechanism.

[0061] In some embodiments, the UAV 300 may comprise a rotor assembly (not shown) to generate lift and thrust. The rotor assembly includes, but is not limited to a rotor hub, a rotor blade, a drive system, a fuselage, and a payload module. In some embodiments, the rotor hub is mounted on the central axis of the fuselage, allowing for rotation around the central axis of the fuselage. The rotor blade is attached to the rotor hub. Further, the rotor blade is rotated to generate the lift and thrust. The drive system is integrated into a power source to impart rotational motion to the rotor blade, enabling the flight operation of the exemplary UAV 300.

[0062] In some embodiments, the fuselage is a rigid structure that comprises one or more components for enabling the flight operation of the UAV 300. One or more components include, but are not limited to, the power source, and a flight control system. The power source is used to provide power to the rotor assembly. In one embodiment, the power source is an electric motor. Further, in some embodiments, the power source is a combustion engine. In some embodiments, the flight control system is used to maintain the stability of the UAV 300. In some embodiments, the flight control system is used for controlling one or more flight parameters. Further, in some embodiments, the flight control system is used to receive and process input commands. The payload module enables the attachment and transportation of one or more payloads. In one embodiment, the payload module is positioned beneath the rotor assembly. In one embodiment, the payload module is centrally located within the fuselage. In one embodiment, the payload module is integrated into a separate compartment. The payload module includes, but is not limited to cameras, sensors, and delivery mechanisms.

[0063] In some embodiments, a variable-pitch mechanism is incorporated in the UAV 300. The variable pitch mechanism allows for dynamic adjustment of the rotor blade's angle during flight. The variable-pitch mechanism enables precise control over the lift and thrust generation. The variable-pitch mechanism provides maneuverability, stability, and responsiveness in bad weather conditions such as snowstorm, heavy rainfall and the like. In some embodiments, the variable-pitch mechanism is used to perform complex flight maneuvers.

[0064] In some embodiments, a gyroscopic stabilization mechanism is incorporated in the UAV 300. The gyroscopic stabilization mechanism provides stability and counteracts a torque generated by rotation of the rotor blade. The gyroscopic stabilization mechanism comprises one or more sensors. The one or more sensors are used to detect and measure an angular movement of the UAV 300. Based on the measured angular mechanism, the flight control system adjusts a rotation speed of rotor blade and a blade pitch of rotor blade for maintaining balance during the flight.

[0065] In some embodiments, a swashplate mechanism is integrated into the UAV 300. The swashplate mechanism allows for cyclic control the pitch of rotor blade at one or more points along a length of rotor blade. By adjusting the pitch of the blade pitch cyclically, the UAV 300 achieves movement in one or more directions such as forward, backward, sideways, rotation, and the like.

[0066] In some embodiments, one or more avionics systems are incorporated in the UAV 300 for controlling and monitoring the flight. The one or more avionics systems comprise one or more sensors, one or more onboard processors, and a communication module. The one or more avionics systems collect data from the one or more sensors such as GPS, altimeters, gyroscopes, accelerometers, and magnetometers, multispectral sensors, thermal sensors to determine an exemplary UAV position, an exemplary UAV altitude, an exemplary UAV orientation and the like. The one or more avionics systems process the collected data to adjust the one or more control surfaces.

[0067] In some embodiments, a communication module facilitates communication between the UAV 300 and a ground control station (GCS). The communication module enables a real-time data transmission, a telemetry monitoring, a control signal exchange, and the like between the UAV 300 and a drone operator. In some embodiments, the communication module employs one or more wireless technologies such as a radio frequency (RF), a satellite communication, one or more cellular networks, and the like to communicate with the GCS.

[0068] In some embodiments, the assignment determined by the system 201a for the UAV of the fleet of UAVs 213al for the mission is transmitted to a controller associated with the UAV. The controller of the UAV is configured to determine a trajectory for the mission based on the received assignment. Further, the controller determines control commands that cause the UAV to track the trajectory. Alternatively, in some embodiments, the system 201a determines the control commands to track the trajectory. The system 201a further transmits determined control commands to the controller. The controller controls the UAV according to the control commands to track the trajectory for the mission.

[0069] As a result, an AGV 110 and a UAV 300 may be controlled independently and/or jointly. The joint control can optimize the overall performance but needs to consider differences in the dynamics of the robots of different types. Planning the motion of a robot that is slow and subject to natural barriers but with long/almost unlimited range (such as AGV) deploying and recovering task-performing robots that are fast and not subject to natural barriers (such as UAV), but with limited range over long mission is potentially challenging. Due to the different dynamics of AGVs and UAVs, fast sampling is needed (since the UAV motion is fast) over a longer horizon (since the overall AGV mission is long). Also, motion planning contains continuous decisions (the motion) and discrete decisions (when to release and when to recover). Also, many trajectories need to be optimized together, and the computational burden usually grows at least polynomially with the number of decision variables. Also, while the range consumption during transfer flight can be easily computed, the range consumption while the mission is being carried out at the target may be hard to compute (e.g., in target monitoring missions, sensing and processing power computation are hard to predict).

[0070] Instead, the AGV motion requires only slow sampling, and the UAVs missions are short. If one can decouple the planning of UAVs and AGV motions the problem can be greatly simplified and the multiple problem solved will be faster than solving a single large optimization problem, due to the polynomial increase of the computation with the decision variables. However, the motion plans of AGVs and UAVs needs to be coordinated because the AGVs needs to deploy and appropriately recover the UAVs, without the UAVs running out of range. So the motion plan of the AGVs needs to be such that recovery of the UAVs within the limits of range from UAV mission target is possible, and similarly the deployment of the UAV is possible, to reach target with sufficient range left to carry out the mission and rendezvous with AGV.

[0071] FIG. 4 shows a pseudo-code of a joint motion control problem for controlling hybrid robots of different dynamics addressed by different embodiments. The joint motion planning problem provides motion trajectoris for an AGV and multiple UAVs to monitor a sequence of targets. The plans of AGV and UAVs are correlated because the UAVs depart from and rendezvous with the AGV for long-distance transport, re-charging, and possibly data dumping. Thus, while the AGV does not need to visit the targets itself, it needs to follow a plan that allows for the recovery of UAVs within the battery range and in a suitable time interval.

[0072] For clarity, the disclosure includes the following notation: , .sub.0+, .sub.+, , .sub.0+, .sub.+ are the sets of real, nonnegative real, positive real, integer, nonnegative integer, positive integer numbers. Intervals are denoted by .sub.[a,b)={z: az<b}, I is the identity matrix, 0 an all-zeros matrix of appropriate dimensions, and Q0, (Q0), a positive (semi) definite matrix. For vectors x, y the stacking is (x, y)=[x].sup.T y.sup.T].sup.T, the 2-norm is .Math..

[0073] For example, some embodiments consider the motion planning of one AGV, with state vector x.sub.g.sup.n.sup.g, and N.sub.a UAVs, with state vectors

[00001]$x_a^{\left(i\right)}{}^{n_a},i{}_{\left[1,N_a\right]}.$

The AGV motion model is

[00002]$\begin{array}{cc}{\stackrel{.}{x}}_g\left(t\right)=f_g\left(x_g\left(t\right),u_g\left(t\right)\right)& \left(1\right)\end{array}$$\begin{array}{cc}{p}_g\left(t\right)=h_g\left(x_g\left(t\right)\right),& \left(2\right)\end{array}$ [0074] where u.sub.g.sup.m.sup.g is the input vector and p.sub.g.sup.2 is the position vector in global coordinates. The choices for the AGV motion model include linear double integrators, unicycle, and bicycle. The AGV is subject to constraints

[00003]$\begin{array}{cc}{x}_g{}_g,u_g{}_g,& \left(3\right)\end{array}$ [0075] where .sub.g .Math..sup.n.sup.g, .sub.g.sup.m.sup.g, are sets defining the admissible state and input vectors, respectively.

[0076] Some embodiments consider quadrotor UAVs with linear motion model

[00004]$\begin{array}{cc}{\stackrel{.}{x}}_a^{\left(i\right)}\left(t\right)=A{x}_a^{\left(i\right)}\left(t\right)+B{u}_a^{\left(i\right)}\left(t\right),& \left(4\right)\end{array}$$\begin{array}{cc}{p}_a^{\left(i\right)}\left(t\right)=C{x}_a^{\left(i\right)}\left(t\right),& \left(5\right)\end{array}$ [0077] where

[00005]$u_a^{\left(i\right)}{}^{m_a}$

is the input vector and

[00006]$p_a^{\left(i\right)}{}^2$

is the UAV position vector in global coordinates, for all i.sub.[1,N.sub.a.sub.]. For instance, (2) may be two double integrators, n.sub.a=4, m.sub.a=2,

[00007]$A=\left[\begin{array}{cc}0& I\\ 0& 0\end{array}\right],B=\left[\begin{array}{c}0\\ I\end{array}\right],C=\left[\begin{array}{cc}I& 0\end{array}\right]$$\mathrm{and}{x}_a^{\left(i\right)}={\left[p_{a,x}^{\left(i\right)},p_{a,y}^{\left(i\right)},v_{a,x}^{\left(i\right)},v_{a,y}^{\left(i\right)}\right]}^{},u_a^{\left(i\right)}={\left[a_{a,x}^{\left(i\right)},a_{a,y}^{\left(i\right)}\right]}^{}.$

For shortness,

[00008]$p_a^{\left(i\right)}=\left(p_{a,x}^{\left(i\right)},p_{a,y}^{\left(i\right)}\right),v_a^{\left(i\right)}=\left(v_{a,x}^{\left(i\right)},v_{a,y}^{\left(i\right)}\right),\mathrm{and}{a}_a^{\left(i\right)}=\left(a_{a,x}^{\left(i\right)},a_{a,y}^{\left(i\right)}\right)$

denote the positon, velocity and acceleration vectors, respectively. The UAVs are subject to constraints on velocity and acceleration

[00009]$.Math.v_a^{\left(i\right)}.Math.v_{\max },{.Math.a_a.Math.}^{\left(i\right)}{a}_{\max },$

for all i.sub.[1,N.sub.a.sub.] that can be written as

[00010]$\begin{array}{cc}{x}_a^{\left(i\right)}{}_a,u_a^{\left(i\right)}{}_a,& \left(6\right)\end{array}$ [0078] where .sub.a.Math..sup.n.sup.a, .sub.g.Math..sup.m.sup.a are the sets of admissible UAVs state and input vectors, respectively. The embodiments of the invention consider the UAVs to be faster than the AGV.

[0079] For simplicity, the disclosed embodiments model the motion of the UAVs in two dimensions, i.e., with a constant flight altitude, but all out developments translate immediately to the 3D case, where a third integrator is added for the altitude dynamics.

[0080] The range of the AGV is assumed to be significantly larger than what needed for the task to be executed, while the UAVs are battery powered and have limited range. For energy consumption during flight, the spent battery energy changes according to

[00011]$\stackrel{.}{}\left(t\right)=c_2{\left(v_a^{\left(i\right)}\left(t\right)\right)}^2+c_1{\left(a_a^{\left(i\right)}\left(t\right)\right)}^2,$

where the embodiments of the invention model the dominant effects of air drag, proportional to the square of the velocity, and losses in accelerating, both mechanical and electrical, modeled as proportional to the squared acceleration. Thus,

[00012]$\begin{array}{cc}{\stackrel{.}{}}^{\left(i\right)}\left(t\right)=x_a^{\left(i\right)}{\left(t\right)}^{}{Q}_e{x}_a^{\left(i\right)}\left(t\right)+u_a^{\left(i\right)}{\left(t\right)}^{}{R}_e{u}_a^{\left(i\right)}\left(t\right),& \left(7\right)\end{array}$ [0081] .sup.(i)(t).sup.(i).sub.max for i.sub.[1,N.sub.a.sub.], where .sub.max is the maximum usable energy. During task execution, the main source of energy consumption is from actuators performing tasks, and sensors, from processing acquired information, and possibly from communicating data to the AGV acting as base station. A prediction model for such consumption is hard to develop, and hence the embodiments of the invention do not rely on it, as it will become clear later.

[0082] The exemplar model (1) ignores the idling and stationary flight energy consumption, to focus on the mission phases when the UAVs are moving. These may be included as constants or ignored if embodiments allow the UAV to land and stop the propellers.

[0083] While the UAV has limited range, it is unaffected by ground obstacles, which impose constraints on the AGV. The exclusion constraints on the AGV are

[00013]$\begin{array}{cc}{p}_g.Math.{}^{\left(o\right)},o{}_{\left[1,N_o\right]},& \left(8\right)\end{array}$ [0084] where N.sub.o is the number of obstacles, and .sup.(o) is the collision region for obstacle o, i.e., the set of AGV positions p.sub.g for which a collision may occur, accounting for the physical shapes of both obstacle and AGV.

[0085] The objective of the AGV and UAVs is to acquire information about a set of targets, j.sub.[1,N.sub.m.sub.] located a known positions

[00014]$p_m^{\left(j\right)}=\left(p_{m,x}^{\left(j\right)},p_{m,y}^{\left(j\right)}\right).$

For that the AGV is to release the UAV carrying the actuators, sensors and communication for performing a task such as monitoring to fly at the monitoring location, acquire data with sensors, process them and send the raw and/or processed data back to the AGV for storage or long distance transmission, the embodiments of the invention assume that the sequence in which targets are to be visited is assigned, and are clustered in groups with know maximum number of elements per cluster.

[0086] Given initial time instant T.sub.0, N.sub.m task location targets with positions

[00015]$p_m^{\left(j\right)}=\left(p_{m,x}^{\left(j\right)},p_{m,y}^{\left(j\right)}\right),j{}_{\left[1,N_m\right]},$

N.sub.O obstacle collision sets .sup.(o).Math..sup.2, o.sub.[1,N.sub.O.sub.], a AGV with motion model (2) subject to (3), (8), initial state x.sub.g(T.sub.0)=x.sub.g,s and desired final state x.sub.g,, and N.sub.a UAVs with motion model (2), energy depletion model (7), subject to (6) and initial states

[00016]$x_{a,s}^{\left(i\right)}=x_{g,s}$

for i.sub.[1,N.sub.a.sub.], determine [0087] a terminal time instant T.sub.>T.sub.0 [0088] time instants

[00017]$t_{\mathrm{ij}}^l,t_{i,j}^b,t_{i,j}^e,t_{i,j}^r,j{}_{\left[1,N_m\right]},i{}_{\left[1,N_a\right]},$ [0089] commands u.sub.g(t) for

[00018]$t\left[T_0,T_f\right],u_a^{\left(i\right)}\left(t\right)$

for

[00019]$t{.Math.}_{j=1}^{N_a}\left[t_{i,j}^l,t{}_{i,j}^b\right].Math.\left[t_{i,j}^e,t{}_{i,j}^r\right],i{}_{\left[1,N_a\right]},$ [0090] such that: [0091] (Timing)

[00020]$t_{i,j}^l{t}_{i,j}^b{t}_{i,j}^e{t}_{i,j}^r$

for all

[00021]$i,j,t_{i,j+1}^l>t_{i,j}^r$

tor all j

[00022]${}_{\left[1,N_m-1\right]},i{}_{\left[1,N_a\right]},t_{i,1}^l{T}_0,t_{i,N_m}^r{T}_f,$

for all i.sub.[1,N.sub.a.sub.] [0092] (UAV traj.)

[00023]$x_a\left(t_{i,j}^l\right)=x_g\left(t_{i,j}^l\right),\left(t_{i,j}^l\right)=0,x_a\left(t_{i,j}^r\right)=x_g\left(t_{i,j}^r\right),\left(t_{i,j}^r\right){}_{\max },$

for all j.sub.[1,N.sub.m.sub.], i.sub.[1,N.sub.a.sub.], and (6) is satisfied. [0093] (task execution) for all j.sub.[1,N.sub.m.sub.], there exists i.sub.[1,N.sub.a.sub.] and

[00024]$t_{i,j}^m$

such that

[00025]$p_a^{\left(i\right)}\left(t\right)=p_m^{\left(j\right)},$

for all

[00026]$t\left[t_{i,j}^b,t_{i,j}^e\right].$ [0094] (AGV trajectory) x.sub.g(T.sub.)=x.sub.g, and (3), (8) are satisfied

[0095] The time instants

[00027]$t_{i,j}^l,t_{i,j}^b,t_{i,j}^e,t_{i,j}^r$

are the launch, beginning of the task execution, end of the task execution and recovery time of UAV i to target j, respectively. For notational simplicity the embodiments of the invention determine such time instants for of all UAVs to each target, but the embodiments of the invention only require one UAV to actually reach the target for task execution, that means that the launch, task execution (beginning and ending), and release time for all the others may be set equal, and hence ignored. the embodiments of the invention determine UAV commands only between launch and beginning of task execution, and between end of task execution and recovery. Between recovery and the next launch the UAVs will be docked with the AGV, and during task execution the UAVs are considered stationary though practically they will use a separate motion strategy to optimize data acquisition.

[0096] In practice, to solve the motion planning problem as a whole may be challenging due to the different time-scales of AGV and UAVs motions, the hybrid nature of the decision variables, i.e., continuous control signals and discrete events such as launch and recovery, and the possibly large number of variables when many UAVs are considered. In what follows the embodiments of the invention develop a method to decouple the motion planning problem for AGV and UAVs while ensuring recovery can be achieved within the UAV safe flight envelope and range.

[0097] To that end, it is an object of some embodiments to address the decentralized planning of the AGV and UAV's motion to ensure that all missions can be accomplished and rendezvous with AGV is feasible within the UAV's limits of range.

Solution Overview

[0098] FIG. 5 shows a schematic of decoupling 510 the joint motion planning problem 400 into an AGV motion planning 530 and UAV motion planning 540 according to some embodiments. To decouple the control of AGV and UAV while allowing both the AGV and UAVs to jointly perform a task, some embodiments use the connection 520 of the state space of the dynamical system and energy of the dynamical system embodied in but not limited to principles of levels of Lyapunov functions.

[0099] Some embodiments are based on the realization that because the AGV and UAV share the state space, the control of the AGV performed in the common state space can be used to constraint the energy depletion of the UAV through the levels of the Lyapunov function of UAV's dynamics. This realization allows decoupling the control of the AGV and UAV to perform a task jointly by using the motion of the AGV as an energy constraint on the operation of the UAV. Such a connection makes the operation of the UAV dependent on the motion of the AGV in a flexible manner that allows independent optimization of the motion of the UAV from optimization of the motion of the AGV.

[0100] Specifically, the level of a Lyapunov function refers to its value at a particular point in the state space of a dynamical system. In the context of stability analysis, a Lyapunov function is a scalar function that can be used to analyze the stability of an equilibrium point of a dynamical system.

[0101] For example, if embodiments have a dynamical system described by the differential equation. {dot over (x)}=(x), where x is the state vector and (x) describes the system dynamics, and if x* is an equilibrium point of the system (i.e., (x*)=0), then a Lyapunov function is a function V(x) such that:

[00028]$\begin{array}{cc}1.& \\ V\left(x^{*}\right)=0\left(\mathrm{the}\mathrm{function}\mathrm{is}\mathrm{zero}\mathrm{at}\mathrm{the}\mathrm{equilibrium}\mathrm{point}\right).& \end{array}$ [0102] V(x)>0 for all xx* in some neighborhood of x* (the function is positive definite). [0103] {dot over (V)}(x)<0 for all x in that neighborhood (the derivative of the function along trajectories of the system is negative/semi-definite).

[0104] As used herein, the level of the Lyapunov function at a point x refers to the value of V(x) at that point. The level can indicate how far the system state is from the equilibrium point and whether the system is moving towards or away from the equilibrium based on the sign of {dot over (V)}(x). If {dot over (V)}(x)<0, the system is moving towards the equilibrium, and if {dot over (V)}(x)>0, the system is moving away from the equilibrium.

[0105] Some embodiments are based on the recognition that the Lyapunov function can be solved to estimate its level sets. In the context of Lyapunov functions, a level set refers to a set of points in the state space of a dynamical system where the Lyapunov function takes a particular value. In other words, for a Lyapunov function V(x), the level set of V at a constant value c is the set of all points x in the state space such that V(x)=c.

[0106] When an equilibrium point of the Lyapunov function of dynamics of a UAV is aligned with a target location of a task, level set c defines the energy needed for the UAV to cover a distance between the target location and state space corresponding to level set c. Because the AGV and UAV share the state space, if the state space corresponding to level set c intersects the motion trajectory of the AGV, it is guaranteed that the UAV can reach the AGV at the point of intersection by spending the amount of energy defined by level c. Accordingly, to guarantee that the UAV has sufficient energy for traversing between the AGV and the target location, there is a need to find the level set of the Lyapunov function of dynamics of a UAV defining a segment of space intersecting the AGV trajectory when an equilibrium point of the Lyapunov function is aligned with a target location of a task. Doing this in such a manner allows controlling the motion of the AGV according to the AGV trajectory while instructing the UAV to perform the task according to its own computations subject to one or a combination of energy constraints governed by the level set of Lyapunov function and time constraints governed by a time instance of the segment of space intersecting the AGV trajectory.

[0107] Such an understanding allows to use energy budget specified for the performance of each task and the energy model of the motion of the UAV to perform the motion planning 540 of the UAV subject to the energy budget and energy model of the UAV 520, and after that to use the planned UAV motion as a constraint to plan the motion of the AGV 530.

[0108] For example, some embodiments are based on realizing that the connection between AGV and UAVs motion is the recovery and launch operations. For these, the main limitation is the range of the UAVs. Hence, the motion plan of AGVs and UAVs can be decoupled by determining the regions that the UAVs can reach based on their remaining range. The regions can be formulated as constraints, and include also other limitations, such as the UAV's speed and acceleration. Then, to ensure safe recovery, the range-dependent constraints can be included in a motion planning problem for the UAVs alone, imposing crossing for at least a time window of a certain length. The problem returns an AGV trajectory and a return range threshold for UAVs such that, if the UAV returns to the AGV before the range (range is energy) is below the threshold in a way that reaches the AGV trajectory in the appropriate window, then rendezvous will safely occur with the available range. Thus, the UAVs can now safely plan their return motion. When the range reaches the lower threshold or when the timing is such that the UAVs reach the AGV at the end of the time window, the UAVs start moving towards AGV. Then, rendezvous will occur. A similar approach can be used for launching decisions, where the range regions are now centered on the target, and the AGV motion is imposed to enter the regions from which the UAVs can reach the target within a range. Once AGV trajectory is decided, re-optimization of UAV trajectory one-by-one is possible which may further reduce range consumption, thus enabling longer time spent executing the mission at the target.

[0109] FIG. 6A shows a block diagram of method 600 for controlling an autonomous ground vehicle (AGV) carrying one or multiple unmanned aerial vehicles (UAVs) to perform one or multiple tasks necessitating visiting one or multiple target locations according to some embodiments. The method uses a processor coupled with stored instructions implementing the method, wherein the instructions, when executed by the processor carry out steps of the method. In some embodiments, method 600 is performed by a control system 201a of FIG. 2A.

[0110] Method 600 collects energy budgets 650 for each of the one or multiple tasks at target locations 660 to be performed by each of the one or multiple UAVs and determines 610, for each of the tasks based on an energy budget 650 collected for a task and an energy model of a UAV assigned to the task, a reachable set 515 defining a region of space including a target location 660 for performing the task that enables the UAV located in the reachable set to reach the target location, spent predetermined energy for performing the task and exit the reachable set while staying within the energy budget and operating within a safe envelope of flight conditions 670.

[0111] In various embodiments, the reachable sets are determined based on the energy model of the UAV 520. However, in addition to using the energy model to determine the reachable sets, the embodiments are based on recognizing that the energy model can also be used to estimate launch and recovery time spans within the reachable set allowing a UAV to reach the target location, perform a task spending energy predetermined for the type of the task, and reach a border of the reachable set for being recovered, i.e., picked up, by the AGV.

[0112] Hence, the embodiments of method 600 determine 620, based on the energy model of the UAV, a difference 625 between a launch time span and a recovery time span of the UAV based on the dimensions of the reachable set and time allocated for the performance of the task corresponding to the energy predetermined for the task. For example, some implementations determine a range of launch time and a range of recovery time with the smallest difference being the minimal time for executing the task.

[0113] Doing this in such a manner allows us to minimize the time needed for the performance of each task while ensuring the feasibility of the completion of the task.

[0114] Next, method 600 determines 630 a AGV motion trajectory as a function of time and space prescribing the AGV to be in a launch location in the reachable set within the launch time span and in a recovery location in the reachable set at the recovery time span subject to a constraint on the difference between the launch time span and the recovery time span. Notably, this approach allows embodiments to determine only ranges for launch time and recovery, then pick the specific locations and/or specific launch and recovery time after solving the AGV motion trajectory.

[0115] Having the AGV motion trajectory, method 600 controls 640 the AGV according to the AGV motion trajectory while commanding the UAV to perform the task upon reaching the launch location at the launch time and collecting the UAV in the recovery location at the recovery time. In some implementations, the control 640 only instructs the UAV about specifics of launch and recovery operations, while allowing controllers of the UAV to perform its own control. In alternative implementations, the control system 201a implemented on the AGV performs the controls of the UAVs.

[0116] FIG. 6B shows a schematic of the architecture of a decoupled motion planning system where the motion planners of UAVs 680, 681, 682 provide the reachable regions 685 to an AGV motion planner 690. In turn, the AGV motion planner 690 computes AGV trajectory crossing such regions during suitable time periods. The trajectory is then provided 695 to separate UAV motion planners 680, 681, 682 that plan motion to the target and from the target to the AGV rendezvous in the reachable region and in the appropriate time windows.

[0117] FIG. 7A shows a schematic illustrating the dependency between the energy budget, energy model, and the task to be performed, with the difference between launch and recovery time spans employed by some embodiments. For example, knowing the dimensions of a reachable set 700 including a target location, the time of flying between target location 750 and the border of the set 700 for the fly-in 710 and fly-out 730 operations depend on energy spent by the UAV and can be calculated based on the energy model as described below. The time 720 for performing the task can be predetermined for the type of the task. Together the sum 740 of the times 710, 720, and 730 can form the minimal difference within launch and recovery time spans allocated for the energy budget.

[0118] FIG. 7B shows a schematic of determining different reachable sets of launch and recovery operations according to some embodiments. Indeed, while some implementations determine a single reachable set 700 illustrated in FIG. 7A, some other implementations determine one reachable set 770 for launch operation and another reachable set 770 for recovery of the UAV. Doing it in such a manner adds flexibility employed by joint optimization.

[0119] While different embodiments employ different techniques for determining reachable sets, the computation of a general reachable set may be difficult or result in a set that is hard to use in the subsequent determination of the motion plan, e.g., the reachable set may be non-convex or defined by a large number of complicated equations involving both continuous and discrete variables. While determining reachable sets can be done using Lyapunov principles, such a determination still can be challenging.

[0120] FIG. 8 shows a schematic illustrating a method for determining a reachable set 800 as an intersection of a Lyapunov stability set 810 defined by a first Lyapunov function and a Lyapunov energy set 820, 830, or 840 defined by a second Lyapunov function, according to some embodiments. Doing this in such a manner allows to separation of flying requirements from energy consumption requirements to simplify the overall computation.

[0121] For example, the Lyapunov stability set is determined for a feedback controller of the UAV and flight constraints defining the safe envelope of flight conditions such that the UAV located within the Lyapunov stability set under the control of the feedback controller reaches an equilibrium for a sublevel set of the first Lyapunov function while satisfying the flight constraints. On the other hand, the Lyapunov energy set is determined for a sublevel set of the second Lyapunov function that describes the energy usage of the UAV controlled by the feedback controller according to the energy model of the UAV. The value of the sublevel set selecting between sets 820-840 is determined by the energy budget.

[0122] The separation between stability and energy requirements allows for flexibility in energy calculations. For example, in different embodiments, the plurality of tasks includes a first task at a first target location and a second task at a second target location, wherein the Lyapunov stability sets for the first and second tasks are determined based on the same values of the sublevel set of the first Lyapunov function and different values of the sublevel set of the second Lyapunov function.

[0123] Indeed, in some embodiments, the Lyapunov stability set is the same for all tasks just with equilibrium varying for different target locations, i.e., the Lyapunov stability set for the first task is determined for the equilibrium aligned with the first target location, and the Lyapunov stability set for the second task is determined for the equilibrium aligned with the second target location. However, the sublevel of the Lyapunov energy set can vary for different tasks.

[0124] In addition, the sets' separation allows for consideration of weather conditions while preserving energy budget constraints. For example, in some embodiments, the processor is operatively connected to a database storing the memory is configured to access different sublevel sets of the first Lyapunov function and different sublevel sets of the second Lyapunov function. The embodiments select the sublevel set of the first Lyapunov function allowing stability satisfying the flight constraints for operating the UAV under current weather conditions, and select the sublevel set of the second Lyapunov function in response to collecting the energy budget.

[0125] FIG. 9 shows a schematic illustrating the additional flexibility of energy-based reachable sets according to some embodiments. As shown in FIG. 9, while an AGV is constrained to be within reachable set 900 for the launch 910 and recovery 920 operations, between that time, the motion trajectory 930 can leave the reachable set 900 to assist in performing other tasks.

Lyapunov-Based Construction of Reachable Regions (Sets)

[0126] While different embodiments employ different techniques for determining reachable sets, the computation of a general reachable set may be difficult, or result in a set that is hard to use in the subsequent determination of the motion plan, e.g., the reachable set may be non-convex or defined by a large number of complicated equations involving both continuous and discrete variables.

[0127] FIG. 10 shows a schematic of a method for determining a reachable set under the special assumption of a linear control method for the linear motion of the UAVs according to some embodiments.

[0128] The embodiments employ control law 1010 for controlling UAV

[00029]$u=K{x}_a,x_a=\left(x_a-x_s\right),$ [0129] and the UAV motion described by linear equations 1020

[00030]${\stackrel{}{x}}_a\left(t\right)=A{x}_a\left(t\right)+B{u}_a\left(t\right),$$p_a\left(t\right)=C{x}_a\left(t\right),$

[0130] Where x.sub.s is the UAV target and x.sub.a is the UAV state, u.sub.a is the UAV control and the matrices A, B, C are known while K is the control law gain to be chosen by design.

[0131] First, the embodiments select feedback gain K such that the closed-loop motion model matrix A+BK is exponentially stable. Specifically, the embodiments determine 1030 K and a first Lyapunov function

[00031]${}_c\left(x_a\right)=x_a^{}{P}_c{x}_a^{}$ [0132] where such function is recognized to be a special case of a Lyapunov function, such that along the closed-loop trajectories

[00032]${\stackrel{}{}}_c\left(x_a\left(t\right)\right)-{}_c\left(x_a\left(t\right)\right),$ [0133] and such that state and input constraints

[00033]${\underset{}{x}}_a{x}_a{\stackrel{}{x}}_a$${\underset{}{u}}_{a}K{x}_a{\stackrel{}{u}}_a$

[0134] Are satisfied for states x.sub.a within the stability region described by

[00034]$x_a^{}{P}_c{x}_a^{}1$

[0135] Then the embodiments construct the energy usage rate according to the energy model 1040

[00035]$\stackrel{}{}\left(t\right)={x_a\left(t\right)}^{}{Q}_e{x}_a\left(t\right)+{u_a\left(t\right)}^{}{R}_e{u}_a\left(t\right),$ [0136] which enables accounting for energy consumption as a function of velocity and acceleration, and determine 1050 the Lyapunov energy set by constructing [0137] the Lyapunov function

[00036]${}_e\left(x_a\right)=x_a^{}{P}_e{x}_a$ [0138] by computing P.sub.e such that it is also a special type of Lyapunov function and P.sub.e is the solution of the Lyapunov equation

[00037]$P_e\left(A+BK\right)+{\left(A+BK\right)}^{}{P}_e=-\left(Q_e+K^{}{R}_{e}K\right)$ [0139] and such that it is positive semi-definite. In addition, imposing

[00038]${}_e\left(x_a\right){}_e$ [0140] the total energy is used to move to x.sub.s from x.sub.a results in an expenditure of energy of less than g.sub.e, according to energy consumption rate model.

[0141] Accordingly, the reachable set 1060 is an intersection of the stability 1030 and energy 1050. For example, FIG. 8 shows an example of region 810 such that

[00039]$x_a^{}{P}_c{x}_a^{}1,$

where the flight constraints are satisfied and of the region .sub.e(x.sub.a).sub.e, 820-840 that limits the energy to move to target and return from target to g.sub.e. As shown in FIG. 8, the energy region changes by increasing or decreasing g.sub.e.

[0142] FIG. 11 shows a schematic of time calculation for launch and recovery operations according to some embodiments.

[0143] Given state dx.sub.1 such that (x.sub.1)=.sub.11, the time to enter into the region of states such that (x)=.sub.2<.sub.1 is computed as

[00040]$\begin{array}{cc}T=-{}^{-1}\ln \frac{{}_2}{{}_1}{}^{-1}\ln {}_2.& \left(8\right)\end{array}$

[0144] Thus, some embodiments use to determine how long is going to take to reach a neighborhood of a task execution target constructed as a level set of the Lyapunov function from the AGV, and conversely how to reach a neighborhood of the AGV from the task execution target. Here .sub.2 is selected as a range such that task execution at a target can be executed using the sensors on board of the UAV from range e.sub.2. This is used to determine 1110 the time for motion of the AGV between UAV launch and recovery, as follows.

[0145] Given a range where the task can be performed .sub.2.sup.T the time bound to reach the position to start the task is computed 1120 as

[00041]$T^T={}^{-1}\ln {}_2^T.$

Similarly, given a range where the landing maneuver of UAV onto AGV can be performed .sub.2.sup.L the time bound to reach AGV landing range from the location of the target of the task execution computed 1140 as

[00042]$T^L={}^{-1}\ln {}_2^L.$

Then, considering a minimum task execution time 1130 T.sub.E, the time between recovery and range 1150 is T.sup.M=T.sup.E+T.sup.T+T.sup.L.

[0146] FIGS. 12A and 12B show schematics of computation of launch and return commands and trajectories based on reachable regions according to some embodiments. The embodiments launch the UAV from the AGV to a target with state x.sub.m, whereas the state includes the target location 1220, when the state of the AGV x.sub.g is 1210 such that

[00043]${}_e\left(x_g-x_m\right){}_e$${}_c\left(x_g-x_m\right)1$

[0147] And plan an initial motion of the UAV by computing the trajectory 1215

[00044]${\stackrel{}{x}}_a\left(t\right)=A{x}_a\left(t\right)+BK\left(x_a\left(t\right)-x_m\right),$$p_a\left(t\right)=C{x}_a\left(t\right),$$x_a\left(0\right)=x_g$

[0148] Similarly, when the UAV is executing task at target 1220, the embodiments command the UAV to return back to the AGV when

[00045]${}_e\left(x_m-x_g\left(t+\right)\right)E\left(t\right)$${}_c\left(x_m-x_g\left(t+\right)\right)1$

[0149] Where E(t) is the remaining energy on board the UAV, tT and T is computed as described above according to the trajectory 1235 connecting the target location 1220 with recovery location 1230 and computed according to

[00046]${\stackrel{}{x}}_a\left(t\right)=A{x}_a\left(t\right)+BK\left(x_a\left(t\right)-x_g\right),$$p_a\left(t\right)=C{x}_a\left(t\right),$$x_a\left(0\right)=x_m$$x_g=x_g\left(t+\right)$

Computation of Energy Budgets

[0150] FIGS. 13A and 13B show schematics of allocating energy budget for performing different tasks by different UAVs according to different embodiments. In the embodiments of FIG. 13A, the UAV is not recharged 1331 and 1332 between the performance of different tasks, and when tasks 1320, 1322, and 1324 from the plurality of tasks are assigned to the UAV; the energy budgets 1330, 1332, and 1332 for performing each of the tasks by the UAV is determined by dividing an energy capacity 1310 of the UAV by a number of the assigned tasks. Additionally or alternatively, when different tasks require different energy, the energy capacity 1310 of the UAV is allocated among the tasks based on their energy requirements.

[0151] FIG. 13B shows a schematic of an embodiment allowing for recharging the UAV between the performance of the tasks. In this embodiment, the energy budget for performing the task by the UAV is determined based on a predetermined value of an energy capacity 1310 of the UAV. An example of the predetermined value is the full capacity or a percentage of the full capacity. To that end, the AGV is controlled to charge the UAV between the recovery time of the task and the launch time of subsequent tasks 1342 and 1344 till the energy capacity of the UAV reaches the predetermined value.

[0152] FIG. 13C shows a flow chart of a method for determining energy budgets dynamically based on the actual performance of the tasks according to some embodiments. The method includes determining 1350 the current level of the energy capacity of the UAV at the recovery time after performing the task; comparing 1360 the current level of the energy capacity with an energy budget allocated for performing a subsequent task and a distance between the recovery location of the task and the launch location of the subsequent task indicative of charging time for recharging the AUV before performing the subsequent task; and updating 1370 the energy budget and the reachable set of the subsequent task based on the comparison. As a result, the energy budget affects the reachable sets of subsequent tasks allowing the tracking of actual energy spending.

Computation of AGV Trajectory Based on Reachable Regions

[0153] Various embodiments determine the AGV motion trajectory by solving an optimization problem minimizing a cost function including a cost of operation of the AGV and a cost of operation of the UAV, to produce the AGV motion trajectory passing through the reachable sets determined for each of the plurality of tasks at appropriate launch and recovery times.

[0154] FIG. 14 shows a pseudo-code of an exemplar optimization method employed by some embodiment. The pseudo-code 1400 solves an optimal motion planning problem that imposes that for each target: [0155] (1) There is a first time instant such that the AGV passes in the area where: [0156] a. the target is reached by satisfying constraints if the linear controller is applied,

[0157] And the target is reached by the UAVs assigned to it with energy usage less than a first threshold, [0158] and there is a second time instant, which is larger than the first time instant with an additional a lower bound of the flight time of the UAV to target, with an additional a lower bound of the time the UAV should spend executing task at the target, and a flight duration such that the AGV passes in the area from which: [0159] it is reached from the target by the UAVs by satisfying constraints if the linear controller is applied [0160] it is reached by the AGV from the target with energy usage less than a second threshold

[0161] The two thresholds are selected such that their sum is less than the initial energy of the drone reduced by an amount of energy to be used at the target for task execution purposes. The thresholds can be fixed or determined as part of the optimal motion planning problem. In the pseudo-code 1400, .sub.g is the motion model of the AGV, F is a terminal cost function and L is a stage, or integrating cost function.

[0162] In some embodiments, the thresholds g.sub.e defining the regions is a decision variable in the motion planning problem, subject to limits, so that the regions can expand and contract, causing longer or shorter flights of UAVs, and hence considering in the cost function the cost of operating the UAV

[0163] In some implementations of the solutions 1400, the optimal motion planning problem is transformed into a numerical problem via time discretization and time scaling, and solved by a numerical optimization solver, such as sequential convex programming or sequential quadratic programming. The result of the solution is an optimal motion trajectory for the AGV, a sequence of control for the AGV that generates such an optimal motion trajectory. The AGV is then controlled to execute such a trajectory either by applying the computed sequence of controls or by providing the computed optimal motion trajectory to a lower-level controller that generates the commands for the AGV to follow said trajectory, while compensating for potential errors in motion of the AGV.

[0164] FIG. 15 shows a block diagram of a method for an iterative estimation of the AGV and UAV initial motion trajectories according to some embodiments. The method determines 1510 the reachable sets defined by functions and the regions where constraints are satisfied and energy to launch and recovery satisfies thresholds and computes 1515 the motion of the AGV such that for each target it enters the region where the UAVs can be launched to reach the target while satisfying energy range and flight constraints, and then a suitable amount of time later it is in the region where the UAVs can be recovered from the target to the AGV position while satisfying energy range and flight constraints.

[0165] The method controls the AGV to move 1520 according to the computed motion and when the AGV enters the region where the UAVs assigned to target i 1525 can be launched to target i, the UAVs is launched 1540 with instructions and/or control commands causing the UAV to fly 1545 to the target. For example, the UAV's motion to the target after launch is generated according to the closed-loop model of the UAV with the linear controller used to define Lyaponove functions of the reachable sets.

[0166] After the UAV performs the task, e.g., he at the second time instant indicative of the end of task execution 1550 the target location, the UAV returns 1555 from target i to the AGV predicted position at the second time instant plus flight time, which is planned to be in the regions to which the UAV can be returned from target i. The UAV motion from the target to the AGV after initiation of return is generated according to the closed loop model of the UAV with the linear controller.

[0167] In some embodiments, the trajectories to the target and from the target are initially computed according to the linear controller. However, after the AGV motion has been fixed, the UAV motion trajectories can be further refined with the aim of reducing energy usage and/or increasing the time at the target. Specifically, once the launch time has been determined, the trajectory to the target can be updated by optimizing the energy and time to reach the target according to the UAV motion model

[00047]$\min w_t{t}_m^i+w_e\left(t\right)$$s.t.{\stackrel{}{x}}_a\left(t\right)=A{x}_a\left(t\right)+B{u}_a\left(t\right))$${\mathrm{Hx}}_a\left(t\right)+L{u}_a\left(t\right))W$$\stackrel{}{}\left(t\right)={x_a\left(t\right)}^{}{Q}_e{x}_a\left(t\right)+{u_a\left(t\right)}^T{R}_e{u}_a\left(t\right),$$\left(t_m^i\right){}_l^i$$x\left(0\right)=x_g\left(t_l^{d\left(i\right)}\right)$$x_a\left(t_m^i\right)x_m^i{}_2$ [0168] where the energy usage threshold G.sub.l.sup.i may be the same as previously or changed to achieve additional objectives.

[0169] Similarly the return trajectory from the task execution target to the AGV can be re-optimized from the one initially computed by the

[00048]$\min w_t+w_e\left(t\right)$$s.t.{\stackrel{}{x}}_a\left(t\right)=A{x}_a\left(t\right)+B{u}_a\left(t\right))$${\mathrm{Hx}}_a\left(t\right)+L{u}_a\left(t\right))W$$\stackrel{}{}\left(t\right)={x_a\left(t\right)}^{}{Q}_e{x}_a\left(t\right)+{u_a\left(t\right)}^{}{R}_e{u}_a\left(t\right),$$\left(\right){}_r^i$$x\left(0\right)=x_m$$x_a\left(\right)=x_g\left(t_r^i+\right)$ [0170] where the energy usage threshold

[00049]${}_r^i$

may be the same as previously or where the energy usage threshold changed to account for the differences in launch trajectory energy usage and/or energy usage at target, and to achieve different objectives.

Exemplar Embodiments and Implementations

Decoupling AGV and UAV Planning Using Reachable Sets

[0171] In order to decouple the planning of AGV and UAVs the exemplar embodiments ensure that after launch from the AGV, the UAVs can accomplish their mission and return to the AGV within the available battery energy and flight envelope constraints. In what follows embodiments focus on the recovery phase, when the UAV must rendezvous with the AGV, before its battery depletes. The method is also applicable to the launch phase, when the UAV reaches the target launching from the AGV, yet embodiments focus on the recovery because then range is a critical constraint. In what follows embodiments refer to a generic UAV and task execution target, so embodiments drop the indices i, j for simplicity.

[0172] The energy usage during flight is known fairly precisely, e.g., can be computed from data on aircraft's pilot operating handbook (POH) by the flight computer or manually using charts, but during task execution it is hard to predict. Thus, embodiments determine the set of states that are reachable from a task execution target position p.sub.m while satisfying flight envelope constraints, for a given return energy budget .sub.e<.sub.max,

[00050]$\begin{array}{cc}\left(p_m,{}_e\right)=\left\{{\stackrel{}{x}}_a{}^{n_a}:t_f<,u_a:\left[0,t_f\right].fwdarw.{}^m,x_a\left(0\right)=\left(p_m,0\right),\left(0\right)=0,x_a\left(t_f\right)={\stackrel{}{x}}_a,\left(t_f\right){}_e,x_a\left(t\right){}_a,u_a\left(t\right){}_a,t\left[0,t_f\right]\right\}.& \left(9\right)\end{array}$

[0173] Then, by imposing on the AGV position

[00051]$\begin{array}{cc}\left(p_g\left(t\right),0\right)\left(p_m,{}_e\right),t\left[t_1,t_2\right]& \left(10\right)\end{array}$ [0174] where t.sub.1, t.sub.2.sub.+ are given, the embodiments of the invention guarantee that if the UAV starts in an appropriate time interval and with remaining energy at least .sub.e, it can execute a feasible rendezvous trajectory from the task execution target to a stationary flight at the AGV position.

[0175] The general reachable set (9) may be hard to compute and the resulting constraint (10), if imposed within optimal control problems, may make their solution challenging. Thus, some embodiments of the invention build more conservative sets, which however are easier to compute and use in optimization.

[0176] The general reachable set (3) may be challenging to compute, and imposing the resulting constraint (3) in an optimal control problem may make its solution challenging. Thus, embodiments build sets that are more conservative but easier to compute and use in optimization.

Reachable Set Construction

[0177] Reachability can be computed efficiently for several classes of sets such as polyhedra, ellipsoids, (constrained) zonotopes. However, some classes are easier to use than others for optimal trajectory generation. Ellipsoids have a compact representation based as a single convex constraint, which make them suitable for optimization. The embodiments of the invention design a fixed linear UAV control law

[00052]$\begin{array}{cc}u=K{x}_a,x_a=\left(x_a-x_s\right),& \left(11\right)\end{array}$ [0178] where x.sub.s=(p.sub.s, 0) is the desired equilibrium, resulting in the asymptotically stable closed-loop dynamics

[00053]$\begin{array}{cc}{\stackrel{}{x}}_a\left(t\right)=\left(A+BK\right)x_a=A_{cl}{x}_a.& \left(12\right)\end{array}$

[0179] Let

[00054]${}_c\left(x_a\right)=x_a^{}{P}_c{x}_a^{},P_{c}0$

be a Lyapunov function for the closed-loop (12), the embodiments of the invention determine .sub.c such that the sublevel set .sub.c={x.sub.a: .sub.c(x.sub.a).sub.c} satisfies .sub.c.Math.{x.sub.a: x.sub.a.sub.a, Kx.sub.a.sub.a}. Then,

[00055]$\begin{array}{cc}{}_c\left(p_m\right)=\left\{x_a=\left(p_a,0\right):{\left(x-x_a\right)}^{}{P}_c\left(x-x_a\right){}_c,x=\left(p_m,0\right)\right\},& \left(13\right)\end{array}$ [0180] is the set of equilibria (p.sub.a, 0) that are reachable from initial state (p.sub.m, 0) by control law (11) without violating state or input constraints.

[0181] Some embodiments compute P.sub.c0 by finding a controller K and a matrix P.sub.c0 that satisfy the exponentially stabilizing Lyapunov linear matrix inequality

[00056]$\begin{array}{cc}AS+S{A}^{}+BY+Y^{}{B}^{}+S0,& \left(13a\right)\end{array}$ [0182] where

[00057]$S=P_c^{-1}$

and Y=KS. Some embodiments of this invention select .sub.c=1 and require

[00058]${}_c=\left\{x_a\text{:}{x}_a^T{P}_{c}x1\right\}.Math.\left\{x_a\text{:}{.Math.v_a.Math.}^2{v}_{\max }^2,{.Math.K{x}_a.Math.}^2{a}_{\max }^2\right\}$

by also imposing that the controller K and the matrix P.sub.c 0 satisfy

[00059]$\begin{array}{cc}0\left[\begin{array}{cc}S& {\mathrm{SG}}_c^T\\ G_{c}S& v_{\max }^{2}I\end{array}\right],0\left[\begin{array}{cc}S& Y^T\\ Y& a_{\max }^{2}I\end{array}\right],& \left(13b\right)\end{array}$ [0183] where G.sub.c selects the appropriate rows for enforcing the velocity bound.

[0184] Some embodiments of the present inventions construct P.sub.c and K by solving the exponentially stabilizing semidefinite program that maximizes the volume of the reachable set .sub.c

[00060]$\begin{array}{cc}\underset{S,Y}{\max }\log \det S& \left(13c\right)\end{array}$$s.t.\left(13a\right),\left(13b\right)$ [0185] and then selecting P.sub.c=S.sup.1 and K=YS.sup.1,

[0186] The reachable set within a given energy budget is computed follows. The energy consumed by the close-loop dynamics (11) to reach a given equilibrium x.sub.s from initial state x.sub.a is

[00061]$\begin{array}{cc}{V}_e\left(x_a\right)={}_0^{}\stackrel{}{}\left(t\right)\mathrm{dt}{}_e.& \left(14\right)\end{array}$

[0187] Then, the sublevel set .sub.e={x.sub.a: .sub.e(x.sub.a).sub.e} includes trajectories with energy usage less than

[00062]${}_e.Math.V_e\left(x_a\right)=x_a^T{P}_e{x}_a$

where P.sub.e 0 is the solution of the autonomous system Lyapunov equation P.sub.e(A+BK)+(A+BK).sup.TP.sub.e=(Q.sub.e+K.sup.TR.sub.eK). Thus,

[00063]$\begin{array}{cc}{}_e\left(p_m,{}_e\right)=\{x_a=\left(p_a,0\right)\text{:}{\left(x-x_a\right)}^T{P}_e\left(x-x_a\right){}_e,& \left(15\right)\end{array}$$x=\left(p_m,0\right)\},$ [0188] is the set of equilibria reached from initial state (p.sub.m, 0) by the control law with energy expenditure less than .sub.e.

[0189] The set

[00064]$\begin{array}{cc}{{}_K\left(p_m,\right)}_e={}_e\left(p_m,{}_e\right).Math.{}_c\left(p_m\right),& \left(16\right)\end{array}$ [0190] is invariant, since for any x.sub.a .sub.c .sub.e, .sub.c(A.sub.clx.sub.a).sub.c (x.sub.a), and .sub.e(A.sub.clx.sub.a).sub.e(x.sub.a) due to the integral in (14), so that A.sub.clx.sub.a .sub.e(p.sub.m,.sub.e).sub.c(p.sub.m). Then, the constraint

[00065]$\begin{array}{cc}\left(p_g,0\right){}_K\left(p_m,{}_e\right),& \left(17\right)\end{array}$ [0191] determines a set of rendezvous positions for the UAV with the AGV, such that the UAV trajectories from stationary flight at the task execution target position p.sub.m to equilibria in such positions satisfy flight envelope constraints and energy budget. The embodiments of the invention consider the rendezvous position as the AGV velocity may briefly stop to allow landing, or the UAV may simply perform a landing on a moving platform.

[0192] Using the exponential stability of .sub.c the embodiments of the invention bound the time for the UAV to reach a neighborhood of the equilibrium, where the rendezvous occurs. Since x.sub.a(t).sup.TPx.sub.a(t)1 for all t.sub.0+, .sub.c(x.sub.a(t)).sub.c(x.sub.a(0))e.sup.te.sup.t. Then, for any .sub.(0,1)

[00066]$\begin{array}{cc}{T}_{\mathrm{rec}}=-{}^{-1}\ln ,& \left(18\right)\end{array}$ [0193] is the upper bound to the time to achieve .sub.c(x.sub.a), that defines the acceptable rendezvous region for E small enough.

Trajectory Optimization for AGV

[0194] Leveraging the reachable set constraints, embodiments can formulate the AGV trajectory generation separately from the UAVs, while ensuring that rendezvous can occur within the range constraints.

[0195] As AGV model (2), embodiments use the kinematic bicycle model

[00067]$\begin{array}{cc}i){\stackrel{}{p}}_g^x=v_g\cos {}_g& \left(19\right)\end{array}$$\mathrm{ii}){\stackrel{.}{p}}_g^y=v_g\sin {}_g$$\mathrm{iii}){\stackrel{}{}}_g=\frac{v_g\tan \left({}_g\right)}{L}$$\mathrm{iv}){\stackrel{.}{v}}_g=a_g,$ [0196] where

[00068]$\left(p_g^x,p_g^y\right)$

is the position, .sub.g is the yaw angle, v.sub.g is the velocity, a.sub.g is the acceleration, .sub.g is the front-steering angle, and L is the wheelbase. The state and input vectors are

[00069]$x_g={\left[p_g^x,p_g^y,{}_g,v_g\right]}^T,u_g={\left[a_g,{}_g\right]}^T,$

respectively.

[0197] For the AGV constraints (2), embodiments consider

[00070]$\begin{array}{cc}i)X_g=\left\{x_g\text{:}0v_g{v}_{\mathrm{gmax}}\right\},& \left(20\right)\end{array}$$\mathrm{ii})U_g=\left\{u_g\text{:}.Math.a_g.Math.a_{\mathrm{gmax}},.Math.{}_g.Math.{}_{\mathrm{gmax}}\right\}.$

[0198] The achievable rendezvous constraint that enforces the AGV to remain inside the reachable set .sub.K(p.sub.m, .sub.e) of the UAV for a time interval is

[00071]$\begin{array}{cc}i)t_1^{\left(j\right)},t_2^{\left(j\right)}\left[T_0,T_f\right]s.t.\left(p_g\left(t\right),0\right){}_K\left(p_m^{\left(j\right)},{}_e^{\left(j\right)}\right),& \left(21\right)\end{array}$$\mathrm{ii}){}_e^{\left(j\right)}{}_{\max },t_2^{\left(j\right)}-t_1^{\left(j\right)}{T}_{\min },t\left[t_1^{\left(j\right)},t_2^{\left(j\right)}\right],$ [0199] where T.sub.min.sub.+ is the minimum duration of the rendezvous window. The upper bound to the energy budget for rendezvous .sub.max<.sub.max/2 is chosen to leave enough energy for launch and task execution.

[0200] Summarizing, the free-final-time optimal trajectory generation problem for the AGV that ensures feasibility of the rendezvous as the optimal control problem

[00072]$\begin{array}{cc}\begin{array}{c}\max \\ x_g(.Math.),u_g(.Math.),{}_e^{\left(j\right)},T_f\end{array}{{}_{T_0}}^{T_f}J\left(x_g\left(t\right),u_g\left(t\right)\right)\mathrm{dt}+w_g\underset{j=1}{\overset{N_m}{.Math.}}{}_e^{\left(j\right)}& \left(22\right)\end{array}$$a)\mathrm{subject}\mathrm{to}\mathrm{optimal}\mathrm{control}\mathrm{constraints}$ [0201] where the optimal control constraints include the motion model of the AGV (19) the constraints on the AGV motion (20), the initial condition of the AGV x.sub.g(T.sub.0)=x.sub.g,s, the terminal condition of the AGV x.sub.g(T.sub.)=x.sub.g,, and constraints on the AGV position to be within the region where the UAV can launch and return with available UAV energy and while satisfying UAV constraints, at times where the UAV can reach the AGV position (21), and the AGV obstacle avoidance constraints (8). In some embodiments of the present invention, the energy threshold Ye is a decision variable of the optimal control problem, and the reachable set shrinks and expand based on the chosen energy threshold. Thus, choosing a larger energy thresholds allows more range for the UAV flight and hence allow release and recovery further away from the target, but reduces the energy available for the execution of the task.

[0202] The cost function J:.sup.n.sup.g.sup.m.sup.g.fwdarw. includes the completion, i.e., final, time and the input energy,

[00073]$J\left(x_g\right)=w_{gt}+w_{ge}{u}_g^{}{u}_{g^{,}}$ [0203] where w.sub.gt, w.sub.ge, w.sub.g.sub.+ are user-defined weights. Constraint (21) involves existential quantifiers for t.sub.1 and t.sub.2 that is not straightforward to include in numerical optimization. Next, we discuss how to implement it using time scaling.

[0204] The cost function J:.sup.n.sup.g.sup.m.sup.g.fwdarw. includes the completion, i.e., final, time and the input energy,

[00074]$J\left(x_g\right)=w_{gt}+w_{ge}{u}_g^{}{u}_g,$ [0205] where w.sub.gt, w.sub.ge, w.sub.g.sub.+ are user-defined weights.

[0206] In order to solve (22) numerically, embodiments discretize it with time scaling. For example, some embodiments use a multiple shooting parameterization ith the adaptive time-mesh

[00075]$T_0=t_0<t_1<.Math.<t_N=T_f,$ [0207] where N is the number of sub-intervals [t.sub.k, t.sub.k+1] for k.sub.[0,N-1], and embodiments introduce time-scaling variables

[00076]$s_k=t_{k+1}-t_k.$

[0208] By parametrizing the control as a first-order hold and integrating in the intervals, the dynamics are

[00077]$\begin{array}{cc}{x}_{k+1}=f_g^{\left(d\right)}\left(x_k,u_k,u_{k+1},s_k\right).& \left(23a\right)\end{array}$ [0209] and the constraints (2) are enforced at node points,

[00078]$\begin{array}{cc}{x}_k{}_g,u_k{}_g,p_{g,k}=h_g\left(x_k,u_k\right).Math.{}^{\left(o\right)},& \left(23b\right)\end{array}$ [0210] for all o.sub.[1,N.sub.o.sub.] and k in .sub.[0,N].

[0211] To implement the rendezvous constraint (10), embodiments first assign consecutive node points

[00079]$\left\{k_1^{\left(j\right)},k_1^{\left(j\right)}+1,.Math.,k_2^{\left(j\right)}\right\}$

to each task execution target j.sub.[1,N.sub.m.sub.]. Then, embodiments formulate (21) as

[00080]$$\begin{gathered} \begin{array}{cc}{.Math.}_{k=k_1^{\left(j\right)}}^{k_2^{\left(j\right)}-1}{s}_k{T}_{\min },{}_e^{\left(j\right)}{}_{\max }, \\ \left(p_{g,k},0\right){}_K\left(p_m^{\left(j\right)},{}_e^{\left(j\right)}\right),k{}_{\left[k_1^{\left(j\right)},k_2^{\left(j\right)}\right]}.& \left(23c\right)\end{array} \end{gathered}$$

[0212] In (23c), even if

[00081]$k_1^{\left(j\right)},k_2^{\left(j\right)}$

are specified, the time instants

[00082]$t_1^{\left(j\right)}\mathrm{and}{t}_2^{\left(j\right)}$

are not fixed, since s.sub.k is a decision variable.

[0213] Thus, the discrete-time formulation of (4) is

[00083]$$\begin{gathered} \begin{array}{cc}\underset{x_k,u_k,s_k,{\left\{{}_e^{\left(j\right)}\right\}}_j}{\max }{w}_{gt}{.Math.}_{k=0}^{N-1}{s}_k+w_{ge}{.Math.}_{k=0}^N{u}_k^T{u}_k+w_g{.Math.}_{j=1}^{N_m}{}_e^{\left(j\right)} \\ s.t.\left(23a\right),\left(23b\right),\left(23c\right),k{}_{\left[k_1^{\left(j\right)},k_2^{\left(j\right)}\right]},j{}_{\left[1,N_m\right]}. \\ {x}_0=x_{g,s},x_N=x_{g,f}.& \left(24\right)\end{array} \end{gathered}$$ [0214] which can be solved by various methods known in the art.

Launch and Recovery Trajectory Optimization for UAVs

[0215] Embodiments, besides generating the UAV recovery trajectories, use the control law to compute the launch instants and launch trajectories, by defining the energy budget to travel to the target and using the task execution target position

[00084]$p_m^{\left(j\right)}$

as an equilibrium of the Lyapunov function.

[0216] Some embodiments further optimize both the launch and recovery of the UAV trajectories which provide additional time/energy for the task execution activities, and/or less time for re-charging at the AGV. Thus, embodiments formulate optimal control problems for launch and recovery that are guaranteed to be feasible since control law holds the trajectory feasible, and it can be used both as an initial guess and as backup, should the optimization not converge in the available time or encounter numerical issues.

Optimization of UAV Recovery Trajectory

[0217] The recovery trajectory planning computes the trajectory of the UAV for returning to the AGV from the task execution target position. Due to the construction in Section 3 such trajectory can be generated easily using the linear control law. Let

[00085]$t{}_{i,j}^r\left[t_1^{\left(j\right)},t_2^{\left(j\right)}\right],$

where

[00086]$t_1^{\left(j\right)},t_2^{\left(j\right)}$

are as in (21), the recovery trajectory is generated as the output of

[00087]$\begin{array}{cc}{\stackrel{}{x}}_a^{\left(i\right)}\left(t\right)=\left(A+BK\right)x_a^{\left(i\right)}\left(t\right)-BK\left(p_g\left(t_{i,j}^r\right),0\right)& \left(25\right)\end{array}$$u_a^{\left(i\right)}\left(t\right)=BK\left(x_a^{\left(i\right)}\left(t\right)-\left(p_g\left(t_{i,j}^r\right),0\right)\right)$$x_a^{\left(j\right)}\left(t_{i,j}^e\right)=\left(p_m^{\left(j\right)},0\right)$ [0218] until

[00088]$t=t_{i,j}^r,\mathrm{where}{t}_{i,j}^e=t_{i,j}^r-T_{\mathrm{rec}}$

is computed according to (8). The task execution operation continues until either

[00089]$t<t_{i,j}^e$

or the remaining energy reaches

[00090]${}_e^{\left(j\right)},$

where, if the latter occurs sooner than the former, the UAV idles until

[00091]$t_{i,j}^e$

at the monitoring target, or start the return trajectory earlier than

[00092]$t_{i,j}^e$

and waits idling, possibly on the ground, at the rendezvous location

[00093]$p_g\left(t_{i,j}^r\right).$

[0219] Due to the construction of the control law and the imposing of constraint (21) on the AGV, the recovery trajectory is guaranteed to achieve the rendezvous condition .sub.c(x.sub.a(p.sub.g, 0)), while satisfying the flight envelope

constraints and within the energy budget

[00094]${}_e^{\left(j\right)}.$

[0220] Further optimization of the recovery trajectory can be achieved to possibly delaying the departure time and/or minimizing the used energy, hence leaving more time/energy for the monitoring operation. We can generate the optimized trajectory by solving

[00095]$\begin{array}{cc}\underset{u_a\left(t\right),{\tilde{t}}_{i,j}^e}{\min }-w_t^r{\stackrel{}{t}}_{i,j}^e+w_e^r\left(t_{i,j}^r\right)& \left(26\right)\end{array}$$s.t.{\stackrel{}{t}}^e{t}^e$$\left(4\right),\left(5\right),\left(6\right),\left(7\right)$$x_a^{\left(i\right)}\left({\stackrel{}{t}}^e\right)=\left(p_m^{\left(j\right)},0\right)$${}_c\left(x_a^{\left(i\right)}\left(t_{i,j}^r\right)-x_g\left(t_{i,j}^r\right)\right)$$\left({\stackrel{}{t}}_{i,j}^e\right)=0,\left(t_{i,j}^r\right){}_e^{\left(j\right)},$ [0221] where

[00096]$w_t^r,w_e^r{}_{++}$

are user-defined weights. Problem (26) is guaranteed to have a feasible solution because the solution computed by (5.1) is feasible, with

[00097]${\stackrel{}{t}}_{i,j}^e=t_{i,j}^e.$

With the newly computed departure time {tilde over (t)}.sup.e and energy (t.sup.r), the UAV can operate for longer at the monitoring location.

Optimization of UAV Launch Trajectory

[0222] The launch trajectory for the UAV starts from the AGV position p.sub.g, reaches the target position

[00098]$p_m^{\left(j\right)}$

and its energy usage must be smaller than .sub.max.sub.max, to save some energy for monitoring. This may be achieved by choosing t.sup.l to avoid releasing the UAV when too far from target, e.g., according to the scenario and AGV trajectory.

[0223] Given the launch time

[00099]$t_{i,j}^l,$

the optimization of the launch trajectory is formulated as

[00100]$\begin{array}{cc}\underset{x_a(.Math.),u_a(.Math.),t_{i,j}^b}{\min }{w}_t^l{t}_{i,j}^b+w_e^l{}_{t^l}^{t^b}\stackrel{.}{}\left(t\right)\mathrm{dt}& \left(27\right)\end{array}$$s.t.\left(4\right),\left(5\right),\left(6\right),\left(7\right)$$x_a\left(t_{i,j}^l\right)=\left(p_g\left(t_{i,j}^l\right),v\left(t_{i,j}^l\right)\right),$$x_a\left(t_{i,j}^b\right)=\left(p_m^{\left(j\right)},0\right),$ [0224] where v=(v.sub.g sin .sub.g, v.sub.g cos .sub.g) is the AGV velocity vector. The cost function in (27) aims at minimizing the flight time and the energy with user-defined weights

[00101]$w_t^l,w_e^l{}_{+}.$

The problem in (27) is a free-final-time optimal control problem subject to convex state and input constraints.

Trajectory Generation and Execution Summary

[0225] An exemplar solution of a decoupled method for AGV-UAV trajectory generation is provided below.

[0226] Parameters: .sub.max, c.sub.1, c.sub.2, .sub.g, .sub.g, .sub.a, .sub.a

[0227] Data:

[00102]$p_m^{\left(j\right)}$

for all j.sub.[0,N.sub.m.sub.], .sup.(o), for all

[00103]$o{}_{\left[0,N_o\right]},x_{g,f},T_0,x_g\left(T_0\right)=x_a^{\left(i\right)}\left(T_0\right)=x_{g,s}$

for all i.sub.[0,N.sub.a.sub.],

[0228] Construct .sub.K, T.sub.rec, K by (16),

[0229] Compute T.sub.,

[00104]${}_e^{\left(j\right)},t_{i,j}^r$

for all j.sub.[1,N.sub.m.sub.], i.sub.[1,N.sub.a.sub.], (x.sub.g(t), u.sub.g(t)) for t[T.sub.0, T.sub.]

[0230] Compute updated

[00105]${}_e^{\left(j\right)},t_{i,j}^e\mathrm{and}\left(x_a^{\left(i\right)}\left(t\right),u_a^{\left(i\right)}\left(t\right)\right)$

for

[00106]$t\left[t_{i,j}^e,t_{i,j}^r\right],$

for all j.sub.[1,N.sub.m.sub.], i.sub.[1,N.sub.a.sub.]

[0231] Compute

[00107]$t_{i,j}^l,t_{i,j}^b\mathrm{and}\left(x_a^{\left(i\right)}\left(t\right),u_a^{\left(i\right)}\left(t\right)\right)$

for

[00108]$t\left[t_{i,j}^l,t_{i,j}^b\right],$

for all j.sub.[1,N.sub.m.sub.], i.sub.[1,N.sub.a.sub.]

[0232] Execute AGV trajectory x.sub.g(t) for t[T.sub.0, T.sub.] i=1: N.sub.a j=1:N.sub.m

[0233] Launch UAV i to target j at

[00109]$t_{i,j}^l$

and execute

[00110]$x_a^{\left(i\right)}\left(t\right)$

for

[00111]$t\left[t_{i,j}^l,t_{i,j}^b\right]$$t[t_{i,j}^l,t_{i,j}^b[\mathrm{and}{}^{\left(i\right)}{}_{m\mathrm{ax}}-{}_e^{\left(j\right)}$

[0234] Execute task at target j with UAV i

[0235] Return UAV i to AGV by

[00112]$x_a^{\left(i\right)}\left(t\right)$

for

[00113]$t\left[t_{i,j}^e,t_{i,j}^r\right]$

[0236] FIG. 16 illustrates a block diagram 1600 of a controller 1601 for the exemplar UAV 1200 according to an exemplary embodiment. The exemplar UAV comprises the controller 1601 for controlling the exemplar UAV 1200. As shown in FIG. 16, the controller 1601 of the UAV 1200 according to an exemplary embodiment may be a computer, a mobile phone, a digital broadcast terminal, a messaging device, a game console, a tablet device, a medical device. Equipment, fitness equipment, personal digital assistants, drone controllers, etc. The controller 1601 includes a processing component 1603, a memory 1605, a power component 1607, a multimedia component 1609, an audio component 1611, an input/output (I/O) interface 1613, a sensor component 1615, and a communication component 1617. The processing component 1603 typically controls the overall operation of the controller 1601, such as operations associated with display, telephone calls, data communications, camera operations, and recording operations. The processing component 1603 can include one or more processors to execute instructions to perform all or part of the steps of the above-described methods. Moreover, processing component 1603 can include one or more modules to facilitate interaction between the components. For example, the processing component 1603 can include a multimedia module to facilitate interaction between the multimedia component 1609 and the processing component 1603. The memory 1605 is configured to store various types of data to support operation at the controller 1601. Examples of data include instructions for any application or method operating on the controller 1601, contact data, phone book data, messages, pictures, videos, and the like. The memory 1605 can be implemented by any type of volatile or non-volatile storage device, or a combination thereof, such as static random access memory (SRAM), electrically erasable programmable read-only memory (EEPROM), or erasable. Programmable Read Only Memory (EPROM), Programmable Read Only Memory (PROM), Read Only Memory (ROM), Magnetic Memory, Flash Memory, Disk or Optical Disk. The power component 1607 provides power to various components of controller 1601. Power component 1607 can include a power management system, one or more power sources, and other components associated with generating, managing, and distributing power for controller 1601.

[0237] The multimedia component 1609 includes a screen between the controller 1601 and the user that provides an output interface. In some embodiments, the screen can include a liquid crystal display (LCD) and a touch panel (TP). If the screen includes a touch panel, the screen can be implemented as a touch screen to receive input signals from the user. The touch panel includes one or more touch sensors to sense touches, slides, and gestures on the touch panel. The touch sensor may sense not only the boundary of the touch or sliding action, but also the duration and pressure associated with the touch or slide operation. In some embodiments, the multimedia component 1609 includes a front camera and/or a rear camera. When the controller 1601 is in an operation mode, such as a shooting mode or a video mode, the front camera and/or the rear camera can receive external multimedia data. Each front and rear camera can be a fixed optical lens system or have focal length and optical zoom capabilities. The audio component 1611 is configured to output and/or input an audio signal. For example, the audio component 1611 includes a microphone (MIC) that is configured to receive an external audio signal when the controller 1601 is in an operational mode, such as a call mode, a recording mode, and a voice recognition mode. The received audio signal may be further stored in memory 1605 or transmitted via communication component 1617. In some embodiments, the audio component 1611 also includes a speaker for outputting an audio signal. The I/O interface 1613 provides an interface between the processing component 1603 and a peripheral interface module, which may be a keyboard, a click wheel, a button, or the like. These buttons may include, but are not limited to, a home button, a volume button, a start button, and a lock button.

[0238] The sensor component 1615 includes one or more sensors for providing various aspects of state assessment for controller 1601. For example, sensor component 1615 can detect an open/closed state of controller 1601, relative positioning of components, such as the display and keypad of controller 1601, and sensor component 1615 can also detect a change in position of one component of controller 1601. The presence or absence of user contact with controller 1601, controller 1601 orientation or acceleration/deceleration, and temperature change of controller 1601. The sensor component 1615 may include proximity transmission A sensor configured to detect the presence of nearby objects without any physical contact. The sensor component 1615 can also include a light sensor, such as a Complementary Metal-Oxide Semiconductor (CMOS) or Charge Coupled Device (CCD) image sensor, for use in imaging applications. In some embodiments, the sensor component 1615 can also include an acceleration sensor, a gyro sensor, a magnetic sensor, a pressure sensor, or a temperature sensor. The communication component 1617 is configured to facilitate wired or wireless communication between controller 1601 and other devices. The controller 1601 can access a wireless network based on a communication standard, such as Wi-Fi, 2G or 3G, or a combination thereof.

[0239] In an exemplary embodiment, communication component 1617 receives broadcast signals or broadcast associated information from an external broadcast management system via a broadcast channel. In an exemplary embodiment, the communication component 1617 also includes a near field communication (NFC) module to facilitate short range communication. For example, the NFC module can be implemented based on radio frequency identification (RFID) technology, infrared data association (IrDA) technology, ultra-wideband (UWB) technology, Bluetooth (BT) technology, and other technologies. In an exemplary embodiment, controller 1601 may be implemented by one or more application-specific integrated circuits (ASICs), digital signal processors (DSPs), digital signal processing devices (DSPDs), programmable logic devices (PLDs), field programmable A gate array (FPGA), controller, microcontroller, microprocessor or other electronic component implementation for performing the above methods. In an exemplary embodiment, there is also provided a non-transitory computer-readable storage medium comprising instructions, such as a memory 1605 comprising instructions executable by the processing component 1603 of the controller 1601 to perform the above method. For example, the non-transitory computer-readable storage medium may be a ROM, a random access memory (RAM), a (Compact Disc-Read Only Memory) CD-ROM, a magnetic tape, a floppy disk, and an optical data storage device. Wherein, when the instructions in the storage medium are executed by the processor, the controller 1601 is enabled to perform the control the exemplary UAV 1200.

[0240] FIG. 17 illustrates a schematic of a computing device 1700 for implementing the system 201a and joint planning methods of the present disclosure, in accordance with an example embodiment. The computing device 1700 includes a power source 1701, a processor 1703, a memory 1705, a storage device 1707, all connected to a bus 1709. Further, a high-speed interface 1711, a low-speed interface 1713, high-speed expansion ports 1715 and low speed expansion ports 1717, can be connected to the bus 1709. In addition, a low-speed expansion port 1719 is in connection with the bus 1709. Further, an input interface 1721 can be connected via the bus 1709 to an external receiver 1723 and an output interface 1725. A receiver 1727 can be connected to an external transmitter 1729 and a transmitter 1731 via the bus 1709. Also connected to the bus 1709 can be an external memory 1733, external sensors 1735, machine(s) 1737, and an environment 1739. Further, one or more external input/output devices 1741 can be connected to the bus 1709. A network interface controller (NIC) 1743 can be adapted to connect through the bus 1709 to a network 1745, wherein data or other data, among other things, can be rendered on a third-party display device, third party imaging device, and/or third-party printing device outside of the computing device 1700.

[0241] The memory 1705 can store instructions that are executable by the computing device 1700 and any data that can be utilized by the methods and systems of the present disclosure. The memory 1705 can include random access memory (RAM), read only memory (ROM), flash memory, or any other suitable memory systems. The memory 1705 can be a volatile memory unit or units, and/or a non-volatile memory unit or units. The memory 1705 may also be another form of computer-readable medium, such as a magnetic or optical disk.

[0242] The storage device 1707 can be adapted to store supplementary data and/or software modules used by the computing device 1700. The storage device 1707 can include a hard drive, an optical drive, a thumb-drive, an array of drives, or any combinations thereof. Further, the storage device 1707 can contain a computer-readable medium, such as a floppy disk device, a hard disk device, an optical disk device, or a tape device, a flash memory or other similar solid-state memory device, or an array of devices, including devices in a storage area network or other configurations. Instructions can be stored in an information carrier. The instructions, when executed by one or more processing devices (for example, the processor 1703), perform one or more methods, such as those described above.

[0243] The computing device 1700 can be linked through the bus 1709, optionally, to a display interface or user Interface (HMI) 1747 adapted to connect the computing device 1700 to a display device 1749 and a keyboard 1751, wherein the display device 1749 can include a computer monitor, camera, television, projector, or mobile device, among others. In some implementations, the computing device 1700 may include a printer interface to connect to a printing device, wherein the printing device can include a liquid inkjet printer, solid ink printer, large-scale commercial printer, thermal printer, UV printer, or dye-sublimation printer, among others.

[0244] The high-speed interface 1711 manages bandwidth-intensive operations for the computing device 1700, while the low-speed interface 1713 manages lower bandwidth-intensive operations. Such an allocation of functions is only an example. In some implementations, the high-speed interface 1711 can be coupled to the memory 1705, the user interface (HMI) 1747, and to the keyboard 1751 and the display device 1749 (e.g., through a graphics processor or accelerator), and to the high-speed expansion ports 1715, which may accept various expansion cards via the bus 1709. In an implementation, the low-speed interface 1713 is coupled to the storage device 1707 and the low-speed expansion ports 1717, via the bus 1709. The low-speed expansion ports 1717, which may include various communication ports (e.g., Universal Serial Bus (USB), Bluetooth, Ethernet, wireless Ethernet) may be coupled to the one or more external input/output devices 1741. The computing device 1700 may be connected to a server 1753 and a rack server 1755. The computing device 1700 may be implemented in several different forms. For example, the computing device 1700 may be implemented as part of the rack server 1755.

[0245] The present disclosure provides the system 201a for controlling the fleet of UAVs. The system 201a determines assignments for one or more UAVS of the fleet of UAVs for delivering a package by performing the multi-stage optimization. In each stage of the multi-stage optimization, different variables pertinent to different participants are optimized. Such a multi-stage optimization ensures correct utilization of the UAVs to provide efficient delivery services. Further, such a multi-stage optimization simplifies the size of each combinatorial problem performed at each stage, thereby the multi-stage optimization is computationally simpler. In other words, complexity involved in performing the multi-stage optimization to schedule and control the UAVs is mitigated/reduced. The embodiments of present disclosure are explained in context of mission service. However, the embodiments of the present disclosure can be applied for other services, such as aerial landscaping services, aerial photography services, surveillance services, and search and rescue services.

[0246] The description provides exemplary embodiments only, and is not intended to limit the scope, applicability, or configuration of the disclosure. Rather, the following description of the exemplary embodiments will provide those skilled in the art with an enabling description for implementing one or more exemplary embodiments. Contemplated are various changes that may be made in the function and arrangement of elements without departing from the spirit and scope of the subject matter disclosed as set forth in the appended claims.

[0247] Specific details are given in the following description to provide a thorough understanding of the embodiments. However, understood by one of ordinary skill in the art can be that the embodiments may be practiced without these specific details. For example, systems, processes, and other elements in the subject matter disclosed may be shown as components in block diagram form in order not to obscure the embodiments in unnecessary detail. In other instances, well-known processes, structures, and techniques may be shown without unnecessary detail in order to avoid obscuring the embodiments. Further, like reference numbers and designations in the various drawings indicated like elements.

[0248] Also, individual embodiments may be described as a process which is depicted as a flowchart, a flow diagram, a data flow diagram, a structure diagram, or a block diagram. Although a flowchart may describe the operations as a sequential process, many of the operations can be performed in parallel or concurrently. In addition, the order of the operations may be re-arranged. A process may be terminated when its operations are completed but may have additional steps not discussed or included in a figure. Furthermore, not all operations in any particularly described process may occur in all embodiments. A process may correspond to a method, a function, a procedure, a subroutine, a subprogram, etc. When a process corresponds to a function, the function's termination can correspond to a return of the function to the calling function or the main function.

[0249] Furthermore, embodiments of the subject matter disclosed may be implemented, at least in part, either manually or automatically. Manual or automatic implementations may be executed, or at least assisted, through the use of machines, hardware, software, firmware, middleware, microcode, hardware description languages, or any combination thereof. When implemented in software, firmware, middleware or microcode, the program code or code segments to perform the necessary tasks may be stored in a machine-readable medium. A processor(s) may perform the necessary tasks.

[0250] Various methods or processes outlined herein may be coded as software that is executable on one or more processors that employ any one of a variety of operating systems or platforms. Additionally, such software may be written using any of a number of suitable programming languages and/or programming or scripting tools, and also may be compiled as executable machine language code or intermediate code that is executed on a framework or virtual machine. Typically, the functionality of the program modules may be combined or distributed as desired in various embodiments.

[0251] Embodiments of the present disclosure may be embodied as a method, of which an example has been provided. The acts performed as part of the method may be ordered in any suitable way. Accordingly, embodiments may be constructed in which acts are performed in an order different than illustrated, which may include performing some acts concurrently, even though shown as sequential acts in illustrative embodiments.

[0252] Further, embodiments of the present disclosure and the functional operations described in this specification can be implemented in digital electronic circuitry, in tangibly embodied computer software or firmware, in computer hardware, including the structures disclosed in this specification and their structural equivalents, or in combinations of one or more of them. Further some embodiments of the present disclosure can be implemented as one or more computer programs, i.e., one or more modules of computer program instructions encoded on a tangible non transitory program carrier for execution by, or to control the operation of, data processing apparatus. Further still, program instructions can be encoded on an artificially generated propagated signal, e.g., a machine-generated electrical, optical, or electromagnetic signal, which is generated to encode information for transmission to suitable receiver apparatus for execution by a data processing apparatus. The computer storage medium can be a machine-readable storage device, a machine-readable storage substrate, a random or serial access memory device, or a combination of one or more of them.

[0253] According to embodiments of the present disclosure the term data processing apparatus can encompass all kinds of apparatus, devices, and machines for processing data, including by way of example a programmable processor, a computer, or multiple processors or computers. The apparatus can include special purpose logic circuitry, e.g., an FPGA (field programmable gate array) or an ASIC (application specific integrated circuit). The apparatus can also include, in addition to hardware, code that creates an execution environment for the computer program in question, e.g., code that constitutes processor firmware, a protocol stack, a database management system, an operating system, or a combination of one or more of them.

[0254] A computer program (which may also be referred to or described as a program, software, a software application, a module, a software module, a script, or code) can be written in any form of programming language, including compiled or interpreted languages, or declarative or procedural languages, and it can be deployed in any form, including as a stand-alone program or as a module, component, subroutine, or other unit suitable for use in a computing environment. A computer program may, but need not, correspond to a file in a file system. A program can be stored in a portion of a file that holds other programs or data, e.g., one or more scripts stored in a markup language document, in a single file dedicated to the program in question, or in multiple coordinated files, e.g., files that store one or more modules, sub programs, or portions of code.

[0255] A computer program can be deployed to be executed on one computer or on multiple computers that are located at one site or distributed across multiple sites and interconnected by a communication network. Computers suitable for the execution of a computer program include, by way of example, can be based on general or special purpose microprocessors or both, and any other kind of central processing unit. Generally, a central processing unit will receive instructions and data from a read only memory or a random access memory or both. The essential elements of a computer are a central processing unit for performing or executing instructions and one or more memory devices for storing instructions and data.

[0256] Generally, a computer will also include, or be operatively coupled to receive data from or transfer data to, or both, one or more mass storage devices for storing data, e.g., magnetic, magneto optical disks, or optical disks. However, a computer need not have such devices. Moreover, a computer can be embedded in another device, e.g., a mobile telephone, a personal digital assistant (PDA), a mobile audio or video player, a game console, a Global Positioning System (GPS) receiver, or a portable storage device, e.g., a universal serial bus (USB) flash drive, to name just a few.

[0257] To provide for interaction with a user, embodiments of the subject matter described in this specification can be implemented on a computer having a display device, e.g., a CRT (cathode ray tube) or LCD (liquid crystal display) monitor, for displaying information to the user and a keyboard and a pointing device, e.g., a mouse or a trackball, by which the user can provide input to the computer. Other kinds of devices can be used to provide for interaction with a user as well; for example, feedback provided to the user can be any form of sensory feedback, e.g., visual feedback, auditory feedback, or tactile feedback; and input from the user can be received in any form, including acoustic, speech, or tactile input. In addition, a computer can interact with a user by sending documents to and receiving documents from a device that is used by the user; for example, by sending web pages to a web browser on a user's client device in response to requests received from the web browser.

[0258] Embodiments of the subject matter described in this specification can be implemented in a computing system that includes a back end component, e.g., as a data server, or that includes a middleware component, e.g., an application server, or that includes a front end component, e.g., a client computer having a graphical user interface or a Web browser through which a user can interact with an implementation of the subject matter described in this specification, or any combination of one or more such back end, middleware, or front end components. The components of the system can be interconnected by any form or medium of digital data communication, e.g., a communication network. Examples of communication networks include a local area network (LAN) and a wide area network (WAN), e.g., the Internet.

[0259] The computing system can include clients and servers. A client and server are generally remote from each other and typically interact through a communication network. The relationship of client and server arises by virtue of computer programs running on the respective computers and having a client-server relationship with each other.

[0260] Although the present disclosure has been described with reference to certain preferred embodiments, it is to be understood that various other adaptations and modifications can be made within the spirit and scope of the present disclosure. Therefore, it is the aspect of the append claims to cover all such variations and modifications as come within the true spirit and scope of the present disclosure.