SYSTEMS, DEVICES, AND METHODS FOR ON-BOARD SENSING AND CONTROL OF MICRO AERIAL VEHICLES

Abstract

Systems, devices, and methods for on-board sensing and control of robotic vehicles (e.g., MAVs) using commercial off-the-shelf hand-held electronic devices as a sensing and control system are provided. In one aspect, a system for controlling a micro aerial vehicle may include one or more sensors, a state estimation module in communication with the one or more sensors, the state estimation module being configured to generate an estimated pose of the micro aerial vehicle based on inputs from the one or more sensors, and a position controller in communication with the state estimation module and configured to communicate attitude commands to an attitude controller of the micro aerial vehicle. Each of the one or more sensors, the state estimation module, and the position controller may be contained in a commercial off-the-shelf hand-held electronic device that is configured to be coupled to the micro aerial vehicle.

Claims

1. A system for controlling a micro aerial vehicle comprising: one or more sensors; a state estimation module in communication with the one or more sensors, the state estimation module being configured to generate an estimated pose of the micro aerial vehicle based on inputs from the one or more sensors; and a position controller in communication with the state estimation module and configured to communicate attitude commands to an attitude controller of the micro aerial vehicle; wherein each of the one or more sensors, the state estimation module, and the position controller are contained in a commercial off-the-shelf hand-held electronic device that is configured to be coupled to the micro aerial vehicle.

2. The system of claim 1, wherein the one or more sensors comprise one or more of a gyroscope and/or an accelerometer.

3. The system of claim 1, wherein the one or more sensors comprise one or more cameras.

4. The system of claim 3, wherein the state estimation module comprises a visual inertial odometry system in communication with the one or more cameras.

5. The system of claim 1, wherein the state estimation module comprises an Unscented Kalman Filter in communication with the one or more sensors, the Unscented Kalman Filter being configured to estimate a full state of the micro aerial vehicle.

6. The system of claim 1, wherein the state estimation module is configured to transmit the estimated pose to the position controller at a rate of about 200 Hz or greater.

7. The system of claim 1, wherein the state estimation module is configured to send visualization data of the estimated pose to a remote user interface.

8. The system of claim 1, wherein the position controller comprises a nonlinear controller.

9. The system of claim 1, wherein the position controller is configured to receive trajectory planning information from a remote user interface.

10. The system of claim 1, wherein the attitude controller is contained in the commercial off-the-shelf hand-held electronic device.

11. A method for controlling a micro aerial vehicle using a commercial off-the-shelf hand-held electronic device, the method comprising: receiving inputs from one or more sensors in the commercial off-the-shelf hand-held electronic device; generating an estimated pose of the micro aerial vehicle based on the inputs from the one or more sensors; generating attitude commands based on the estimated pose of the micro aerial vehicle; and communicating the attitude commands to a control component of the micro aerial vehicle; wherein receiving inputs, generating an estimated pose, and generating attitude commands are all performed on the commercial off-the-shelf hand-held electronic device.

12. The method of claim 11, wherein receiving inputs from one or more sensors comprises receiving inputs from one or more of a camera, a gyroscope, and/or an accelerometer.

13. The method of claim 11, wherein generating an estimated pose comprises using visual inertial odometry to localize dynamics of a body of the micro aerial vehicle with respect to an inertial frame.

14. The method of claim 11, wherein generating an estimated pose comprises applying an Unscented Kalman Filter to the inputs from one or more sensors to estimate a full state of the micro aerial vehicle.

15. The method of claim 11, wherein generating attitude commands further comprises receiving trajectory planning information from a remote user interface.

16. The method of claim 11, wherein generating attitude commands further comprises coordinating a trajectory plan with at least one additional micro aerial vehicle.

17. The method of claim 16, wherein coordinating a trajectory plan comprises: at a remote user interface, determining an optimum solution for a system of equations that represent straight-line trajectories of each of the micro aerial vehicle and the at least one additional micro aerial vehicle; sending coefficients of a respective one of the system of equations to the micro aerial vehicle; and generating the attitude commands based on the coefficients.

18. The method of claim 11, wherein the control component is contained in the commercial off-the-shelf hand-held electronic device.

19. The method of claim 11, further comprising sending visualization data of the estimated pose to a remote user interface.

20. The method of claim 19, wherein the visualization data of the estimated pose comprises point clouds.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0011] The features and advantages of the present subject matter will be more readily understood from the following detailed description which should be read in conjunction with the accompanying drawings that are given merely by way of explanatory and non-limiting example, and in which:

[0012] FIGS. 1A and 1B are perspective side views of a micro aerial vehicle incorporating a commercial off-the-shelf hand-held electronic device as its sensing and control system according to an embodiment of the presently disclosed subject matter;

[0013] FIG. 2 is a block diagram of a control system architecture for the use of a commercial off-the-shelf hand-held electronic device as a sensing and control system for a micro aerial vehicle according to an embodiment of the presently disclosed subject matter;

[0014] FIG. 3 is a perspective side view of a system model for a micro aerial vehicle incorporating a commercial off-the-shelf hand-held electronic device as its sensing and control system according to an embodiment of the presently disclosed subject matter;

[0015] FIG. 4 is a graph illustrating observations of a stationary feature at multiple time instants according to an embodiment of the presently disclosed subject matter;

[0016] FIG. 5 is a graph illustrating a point cloud from a VIO system generated according to an embodiment of the presently disclosed subject matter;

[0017] FIG. 6 is a series of graphs illustrating Cartesian 3D position of the vehicle, with Vicon data, VIO estimates, and UKF estimates generated according to an embodiment of the presently disclosed subject matter;

[0018] FIG. 7 is a series of graphs illustrating Cartesian velocities of the vehicle, with the Vicon data, VIO estimates, and UKF estimates;

[0019] FIG. 8 is Cartesian 3D position of the vehicle, with Vicon data, VIO estimates, and UKF estimates;

[0020] FIG. 9 is a series of graphs illustrating Cartesian positions of the vehicle with Vicon data, VIO estimates, and UKF estimates;

[0021] FIG. 10 is a graph of orientation error of the vehicle with respect to the motion capture system, VIO estimates, and UKF estimates;

[0022] FIG. 11 is a series of graphs illustrating Cartesian velocities of the vehicle with the Vicon data and UKF estimates;

[0023] FIG. 12 is a three-dimensional reconstruction of the flight of three vehicles generating linear motions in a space according to an embodiment of the presently disclosed subject matter;

[0024] FIG. 13 is a three-dimensional reconstruction of the flight of three vehicles generating triangular shapes in a space according to an embodiment of the presently disclosed subject matter; and

[0025] FIG. 14 is a three-dimensional reconstruction of the flight of three vehicles generating rotations in a space according to an embodiment of the presently disclosed subject matter.

DETAILED DESCRIPTION

[0026] In contrast to the shortcomings of on-board control and sensor suites used in conventional micro aerial vehicles, the price/performance ratio of sensors and processors in consumer grade technology seen in cameras and phones has fallen dramatically over the last decade. In particular, most commercial off-the-shelf (COTS) hand-held electronic products like smartphones are packaged with high-resolution cameras, gyroscopes, and accelerometers, all of which may be useful as sensors for aerial robotics. In addition, the low mass and small form factor of such consumer-grade electronics make them particularly well suited for autonomous flight with small flying robots, especially in GPS-denied environments. In this way, micro aerial vehicles may be stabilized and controlled to achieve autonomous flight in indoor buildings with application to smart homes, search and rescue, construction, and architecture. Such vehicles may thus allow a consumer to combine a commercially available robot platform (e.g., a quadrotor) with a COTS hand-held electronic product, download an app, and autonomously drive the robot without GPS and build 3-D maps.

[0027] Accordingly, the present subject matter provides fully autonomous vehicles into which such commercial off-the-shelf hand-held electronic products are integrated as the control and sensor suite. Specifically, in one aspect, the present subject matter provides a system for controlling a micro aerial vehicle with a commercial off-the-shelf electronic product. For example, FIGS. 1A and 1B both illustrate systems in which an off-the-shelf micro aerial vehicle, generally designated 100, is coupled to a hand-held electronic product 200 (e.g., a smartphone). In these embodiments, micro aerial vehicle 100 has a configuration of a conventional quadrotor platform made from carbon fiber commercial off-the-shelf components and is equipped with four brushless motors 102 that are arranged about a housing 110 and that are each configured to drive a corresponding one of four rotors 104 and associated propellers 105. Micro aerial vehicle 100 being a quadrotor has advantages of mechanical simplicity and ease of control. Moreover, its ability to operate in confined spaces, hover at any given point in space, and perch or land on a flat surface makes it a very attractive aerial platform with tremendous potential.

[0028] Housing 110 is configured to surround a control component 120 (e.g., an AutoPilot board) that is configured to control the operation of motors 102. In this regard, control component 120 may include any of a variety of components, including one or more transceivers, power regulators, and motor drivers. In addition, in some embodiments, control component 120 comprises an IMU (e.g., an InvenSense MPU-6050) and a user-programmable microcontroller (e.g., a ARM microcontroller), although the functions of these components can be offloaded onto hand-held electronic component 200 in some configurations. In addition, those having skill in the art will recognize that the particular layout, size, or other configuration of control component 120 may be adapted as needed based on the desired characteristics of micro aerial vehicle 100.

[0029] Furthermore, control component 120 is designed to interface with hand-held electronic component 200, which is coupled to micro aerial vehicle 100 to provide both a sensor array and a control system for micro aerial vehicle 100. In the embodiments illustrated in FIGS. 1A and 1B, for example, hand-held electronic component 200 is mounted above housing 110 on a support structure 112. In particular, in some embodiments, support structure 112 is sized and/or otherwise configured such that hand-held electronic component 200 is spaced a distance apart from housing 110 such that the field of view of one or more of the sensors contained in hand-held electronic component 200 is substantially unobstructed by micro aerial vehicle 100 (e.g., not obstructed by the movement of rotors 104 and/or propellers 105). Alternatively, instead of being mounted above housing 110, those having ordinary skill in the art will recognize that hand-held electronic component 200 may be coupled to micro aerial vehicle 100 in any of a variety of other arrangements, such as on or below housing 110. In any arrangement, micro aerial vehicle further comprises a communications link 114 (e.g., a USB-serial cable) that provides communication between hand-held electronic component 200 and control component 120.

[0030] Regarding the particular form of hand-held electronic component 200 that is coupled to micro aerial vehicle 100, in some embodiments, hand-held electronic component 200 is a specialty device (e.g., Google Tango). In this configuration, hand-held electronic component 200 may incorporate an enhanced camera (e.g., RGB-D), which is some embodiments includes a fisheye lens that has a wide field of view (e.g., up to 170 degrees or greater). In addition, hand-held electronic component 200 may further include a high quality IMU and/or a depth sensor that is able to capture a dense set of point clouds. Such a set of specialized sensors may allow the extraction of depth and solve the scale problem that affects monocular visual odometry algorithms. In addition, the state estimation, control, and planning may be done on a second independent component (e.g., an Odroid-XU board) with additional onboard vehicle sensors.

[0031] Alternatively, in some embodiments, hand-held electronic component 200 is a commercial off-the-shelf smartphone (e.g., a Samsung Galaxy S5). As discussed above, modern smartphones commonly include high-resolution cameras, gyroscopes, and accelerometers, which can be used as a sensor array for micro aerial vehicle 100. This subject matter represents the first plug and play integration of a consumer product with an off-the-shelf aerial robot to enable autonomy with possible onboard localization, mapping, and control. Thus, it is representative of a new class of affordable smart devices that can potentially lower the barrier to automation into homes by providing services for localization, state estimation, control, and mapping. Any end user may be able to utilize his smartphone device to autonomously control an aerial platform and to add new functionalities.

[0032] In any configuration, the total mass of the platform may be less than about 750 g. This reduction in the mass of micro aerial vehicle 100 compared to conventional quadrotor designs is at least partially attributable to the use of hand-held electronic component 200 in place of conventional sensing and control elements. Although many of the particular embodiments discussed herein provide a particular smartphone as the control and sensor system, those having skill in the art will recognize that the configuration discussed herein is independent of the specifics of the hand-held electronic device employed.

[0033] Regardless of the particular physical configuration, hand-held electronic component 200 is configured to run some or all of the computation, sensing, and/or control of micro aerial vehicle 100. In particular, hand-held electronic component 200 incorporates software (e.g., embedded in an app) for control, planning, and tracking the full 3-dimensional motion of micro aerial vehicle 100. In addition, such a system may further be configured to concurrently create a map of the environment using visual odometry and structure from motion algorithms. Thus, in contrast to existing algorithms, which need a large platform and customized hardware processors that can be heavy and expensive, the systems and methods discussed herein provide that a commercial off-the-shelf smartphone or similar device is able to provide full autonomy for an aerial robotic platform. In addition, in some embodiments, the system uses less than 50% of the total CPU available on hand-held electronic component 200, giving the possibility to execute all the tasks on a less powerful device without limitations and/or to add other functionalities in the future.

[0034] Regarding the particular configuration of hand-held electronic component 200 that enables it to run some or all of the computation, sensing, and/or control of micro aerial vehicle 100, FIG. 2 illustrates a schematic representation of a sensing and control system for use with micro aerial vehicle 100. As shown in FIG. 2, the sensing and control system includes a position and attitude controller 210 and a state estimation module 220, which may include a visual inertial odometry (VIO) system 222 for processing images and an Unscented Kalman Filter (UKF) 224 configured to deal with control constraints for fast motions.

[0035] In this arrangement, VIO system 222 and UKF 224 receive inputs from one or more elements of a sensor array 230 provided on hand-held electronic component 200. In particular, for example, sensor array 230 may comprise one or more cameras 232 and/or an IMU 234, which may include one or more gyroscope and/or accelerometer. Then, position and attitude controller 210 receives the estimated pose from UKF 224 and sends the attitude commands to control component 120 on micro aerial vehicle 100. Alternatively, rather than attitude commands being processed by a separate microcontroller on micro aerial vehicle 100 (e.g., control component 120), the attitude control can be handled by the hand-held electronic product 200. As discussed above, these elements may be provided as software that runs as a single app on hand-held electronic component 200.

[0036] To provide an interaction with hand-held electronic component 200 and thus with micro aerial vehicle 100, a remote (e.g., ground station) interface device 250 may also be provided. In some embodiments, for example, interface device 250 may be a computer running a ROS-based interface. Alternatively, in some embodiments, interface device 250 may comprise a remote device (e.g., another smartphone and/or a tablet) running another app, which may be appealing for naive users. In any configuration, interface device 250 may be configured to show the reconstructed environment and/or the estimated 3D path. In particular, for example, hand-held electronic device 200 may be configured to generate sparse point clouds (e.g., as an output from VIO system 222), which can be reconstructed by interface device 250 to provide a visualization of the path of micro aerial vehicle 100.

[0037] In addition, interface device 250 may be configured to send high level commands and/or change control and flight parameters settings. In particular, for example, interface device 250 may be configured to communicated with a trajectory planner 212 on hand-held electronic component 200, which develops a planned trajectory to be navigated by micro aerial vehicle 100. This planned trajectory may then be provided as a further input to position and attitude controller 210. The communication between interface device 250 and hand-held electronic component 200 may be realized via user datagram protocol (UDP) and may be running in a separate thread to not affect estimation and control.

[0038] Regardless of the particular form of interface device 250 with which a user may interact with micro aerial vehicle 100, in some embodiments, hand-held electronic component 200 is configured such that all algorithms are run on board. In this way, interface device 250 is responsible only for visualization and/or handling user interaction. All the tasks involving navigation, control, planning, and estimation may then be executed on hand-held electronic component 200. In some embodiments, the estimation, control, and planning may be realized in separate threads to guarantee real-time reliability.

[0039] Although discussion of particular embodiments and implementations of the subject matter disclosed herein is provided below, those having ordinary skill in the art should recognize that the underlying concepts are not limited to these particular embodiments. Rather, the present subject matter can be applied to any of a variety of further configurations in which a consumer electronic device is configured to perform navigation, control, planning, and estimation with its own embedded sensors (e.g., with camera-IMU and other sensors).

System Model

[0040] Regarding the particular control provided for micro aerial vehicle 100, it is first useful to define the system model that governs its operation. A quadrotor is a system made of four substantially identical rotors 104 located at the vertices of a square. The first and third propeller rotate clockwise, the second and fourth propeller rotate counterclockwise. (See, e.g., FIG. 3) As illustrated in FIG. 3, for an inertial reference frame denoted by {{right arrow over (e)}.sub.1;{right arrow over (e)}.sub.2;{right arrow over (e)}.sub.3} and a body reference frame centered in the center of mass of the vehicle denoted by R=[{right arrow over (b)}.sub.1,{right arrow over (b)}.sub.2,{right arrow over (b)}.sub.3] where RSO(3), the dynamic model of micro aerial vehicle 100 can be expressed as follows:

{dot over (x)}=v,

m{dot over (v)}=Re.sub.3+mge.sub.3,

{dot over (R)}=R{circumflex over ()},

J{dot over ()}+J=M,(1)

where x.sup.3 is the Cartesian position of the vehicle expressed in the inertial frame, v.sup.3 is the velocity of the vehicle in the inertial frame, m is the mass, .sup.3 is the angular velocity in the body-fixed frame and J.sup.33 is the inertia matrix with respect to the body frame. The hat symbol denotes the skew-symmetry operator according to {circumflex over (x)}y=xy for all x,y.sup.3, g is the standard gravitational acceleration and e.sub.3=[0 0 1].sup.T. The total moment M=[M.sub.1 M.sub.2 M.sub.3].sup.T, along all axes of the body-fixed frame and the thrust are control inputs of the plant. The dynamics of rotors and propellers are neglected and it is assumed that the force of each propeller is directly controlled. The total thrust, =.sub.j=1.sup.4f.sub.j, acts in the direction of the z-axis of the body-fixed frame, which is orthogonal to the plane defined by the centers of the four propellers. The relationship between single motor force f.sub.j, the total thrust and the total moment M can be written as follows:

[00001]$\begin{array}{cc}\left[\begin{array}{c}\\ M_1\\ M_2\\ M_{3.Math.}\end{array}\right]=\left[\begin{array}{cccc}1& 1& 1& 1\\ 0& -d& 0& d\\ d& 0& -d& 0\\ -c& c& -c& c\end{array}\right]\left[\begin{array}{c}{f}_1\\ f_2\\ f_3\\ f_{4.Math.}\end{array}\right]& \left(2\right)\end{array}$

where c is a constant value and d is the distance from the center of mass to the center of each rotor in the {right arrow over (b)}.sub.1,{right arrow over (b)}.sub.2 plane. For non-zero values of d, the above equation (2) may be inverted. The assumption that and M are the inputs of the plant is therefore valid.

[0041] Based on this dynamic model, a control scheme may be developed to be performed by position and attitude controller 210. In most previous works, a back-stepping approach is used for control because the attitude dynamics can be assumed to be faster than the dynamics governing the position, and linearized controllers are used for both loops. Where it is desirable to model large excursions from the hover position for robustness, however, a nonlinear controller may be used.

[0042] In such a model, the control inputs , M may be chosen as follows:

M=k.sub.Re.sub.Rk.sub.e.sub.+JJ({circumflex over ()}R.sup.TR.sub.C.sub.CR.sup.TR.sub.C{dot over ()}.sub.C),(3)

=(k.sub.xe.sub.xk.sub.ve.sub.vmge.sub.3+m{umlaut over (x)}.sub.d).Math.Re.sub.3,(4)

where {umlaut over (x)}.sub.d is the desired acceleration, g is the gravity acceleration, k.sub.x, k.sub.v, k.sub.R, k.sub. are positive definite terms. The subscript C denotes a command value, and the orientation and angular rate errors are represented by the following quantities:

[00002]$\begin{array}{cc}{e}_R=\frac{1}{2}.Math.{\left(R_C.Math.R-R^T.Math.R_C\right)}^V.Math..Math.\mathrm{and}.Math..Math.e_{}=-R^T.Math.R_C.Math.{}_C,& \left(5\right)\end{array}$

while translation errors may be represented by the following:

e.sub.x=xx.sub.d and e.sub.v={dot over (x)}{dot over (x)}.sub.d,(6)

where the symbol represents the vee map (3).fwdarw.R.sup.3, which is the inverse of the operation denoted by the symbol . If the initial attitude error is less than 90, the zero equilibrium of the tracking errors is exponentially stable (i.e., [e.sub.x; e.sub.v; e.sub.; e.sub.R][0; 0; 0; 0]). Further, if the initial attitude error is between 90 and 180, then the zero equilibrium of the tracking errors is almost globally exponentially attractive.

State Estimation

[0043] With this model, a 6-degree-of-freedom pose of micro aerial vehicle 100 in the inertial frame is defined, which is used to control micro aerial vehicle 100. The subscripts c, b, and s denote the camera, body, and inertial frame, respectively, while a and g denote accelerometer and gyros quantities. Without loss of generality, in the following, the body frame defined above is coincident with the IMU frame. The symbol R.sub.bc denotes the orientation of frame c with respect to frame b.

[0044] A. Visual Inertial Odometry

[0045] Although previous work has been done on implementing vision based algorithms on camera phones, many of these algorithms rely on marker tracking and/or localization algorithms. Although such algorithms may be considered suitable for augmented reality applications, they are not suitable to deal with long term operations and large navigation coverage areas that are desired in robotic tasks. In addition, although good results on camera phones have been obtained considering rolling shutter effects, the images in such a configuration are collected at a slower rate (e.g., about 15 Hz) and processed later. In contrast, the present subject matter is particularly designed to address these issues and achieve autonomous flight based on a phone or other similar device.

[0046] In this regard, the goal of VIO system 222 is to localize the dynamics of the body with respect to the inertial frame using the accelerometers and gyroscopes of IMU 234 as interoceptive sensors and camera 232 as an exteroceptive sensor. The navigation state vector x(t).sup.12se(3) is defined as follows:

x=[x.sub.sb.sup.T .sub.sb.sup.T v.sub.sb.sup.T .sup.T b.sub.g.sup.T b.sub.a.sup.T].sup.T,(7)

[0047] where x.sub.sb.sup.3 denotes the vector from the origin of the inertial frame to the origin of the b frame expressed in the inertial frame, v.sub.sb is its time derivative, .sub.sb is the attitude vector in exponential coordinates, is the unknown gravity vector in the inertial frame, and b.sub.a and b.sub.g denote slowly changing accelerometer and gyroscope biases. Since camera 232 and IMU 234 are both contained in hand-held electronic component 200, this model assumes that the relative transformation between camera and accelerometer is known. However, with some calibration parameters, such as inertial sensor scale factor, nonorthogonality, camera-accelerometer transformation (x.sub.bc,.sub.bc) are jointly estimated by appending them to the state. The kinematics of equation (7) above can be derived as follows:

{dot over (x)}.sub.sb=v.sub.sb,(8)

{dot over (R)}.sub.sb=R.sub.sb.sup.b{circumflex over ()}.sub.sb,(9)

{dot over (v)}.sub.sb=a,(10)

{dot over ()}=n.sub.,(11)

{dot over (b)}.sub.g=n.sub.bg,(12)

{dot over (a)}.sub.b=n.sub.ba,(13)

where .sup.b.sub.sb=R.sub.bg.sub.sg is the angular velocity of the body frame relative to the inertial, expressed in the body frame, and (n.sub.bg, n.sub.ba, n.sub.) denotes the random walk parameters for biases and gravity.

[0048] The inputs to the dynamic system (a, .sup.b.sub.sb are as follows:

y.sub.a=A.sub.aR.sub.sb.sup.T(y.sub.ab.sub.an.sub.a)+,(14)

y.sub.g=A.sub.g.sub.sg+b.sub.g+n.sub.g,(15)

[0049] where a(t) denotes the acceleration of the body relative in the inertial frame, .sub.sg denotes the angular velocity of the gyroscope relative to the inertial frame (expressed in the IMU frame), n.sub.a and n.sub.g denote additive sensor noise and A.sub.a and A.sub.g characterize the effects of non-unit scale and nonorthogonality of the sensor axes. Errors in a mechanization of Equations (8) and (13) grow in an unbounded fashion, necessitating integration of sensor with bounded errors. In other words, even a tiny drift rate in the gyros results in a slowly growing tilt error. (i.e., The horizontal acceleration error is 9.8 m/s.sup.2 times the tilt error in radians. Double integrating this increasing acceleration error produces a position error which grows cubically in time) Thus, while small inertial sensors can maintain accuracy of a few millimeters for one second, the drift will be hundreds of meters after just a minute or so.

[0050] To address this drift, VIO system 222 is used to update the state estimate by referencing the absolute position and orientation of micro aerial vehicle 100 (i.e., as observed by camera 232). In the past decade, camera measurements have been effectively used to aid Inertial Navigation Systems. It is assumed that the world is populated with several distinguishable features that can be easily tracked over time using a camera. If T.sub.f.sup.T(t)=[x y z] denotes the vector to the feature in the camera frame at time t, the measurement of the camera (normalizing for its intrinsic parameters) is given by the standard perspective projection model:

[00003]$\begin{array}{cc}{y}_c=\frac{1}{z}\left[\begin{array}{c}x\\ y\end{array}\right]+n_c,& \left(18\right)\end{array}$

where n.sub.c is pixel measurement noise.

[0051] For example, as illustrated in FIG. 4, if a feature f is tracked at each t.sub.i, i=0, . . . 3, then the camera measurements y.sub.c(t.sub.i) of the feature provide constraints on the states x(t.sub.i) during that interval. Let F denote the integral function corresponding to Equations (8) and (13) such that

x(t.sub.i)=F(x(t.sub.0),u,t.sub.i),(19)

[0052] where u is the set of all inertial measurements in (t.sub.0, ti). In this way, estimates for {tilde over (x)}(t.sub.i) may be computed that minimize some cost function (y.sub.c(t.sub.i), x(t.sub.i), T.sub.f(t.sub.0)) subject to x(t.sub.i)F(x(t.sub.0),u,t.sub.i).sub.P.sub.i< where P.sub.i is a positive definite matrix and >0. In the disclosed implementation, it is assumed that the sensor measurement noises and random walk parameters are Gaussian distributed. Linearizing F around a nominal trajectory {tilde over (x)}(t.sub.i), we derive the linearized error state integration in the form

x(t.sub.i)=.sub.ix(t.sub.0)+u,(20)

where

[00004]${}_i=\frac{F}{x}$$\mathrm{and}$$=\frac{F}{u}.$

Using equation (20) and the Gaussian noise assumption, the optimization is solved adaptively in error state domain as a Maximum-A-Posteriori estimator leading to the well known Extended Kalman Filter updates.

[0053] If the stationary feature is found to be persistent (e.g., a point tracked at the end of a corridor while navigating towards it), then the feature vector may be augmented along with the pose of the body frame at which it was first observed to the state x in order to correctly account for correlations of errors in subsequent measurements of the feature to errors in the state vector. For example, if it is assumed that features T.sub.f.sub.1(t.sub.1), T.sub.f.sub.1(t.sub.2) (which were first observed in frames c(t.sub.1) and c(t.sub.2) respectively) are tracked, then the augmented state vector x.sub.aug(t) at some tt.sub.1, t.sub.2 would be as follows:

x.sub.aug.sup.T(t)=[x.sup.T(t) x.sub.sb.sup.T(t.sub.1) .sub.sb.sup.T(t.sub.1) x.sub.sb.sup.T(t.sub.2) . . . .sub.sb.sup.T(t.sub.2) T.sub.f.sub.1.sup.T(t.sub.1) T.sub.f.sub.1.sup.T(t.sub.2)]

The measurements y.sub.c(t) of features f.sub.1 and f.sub.2 at time instant t would be used to compute an estimate of x.sub.aug as follows:

{tilde over (x)}.sub.aug(t)=arg min.sub.x.sub.aug(y.sub.c(t),x.sub.aug(t)),

subject to the dynamical constraints imposed by Equation (19)

B. Unscented Kalman Filter

[0054] To enable onboard control, a second estimator is used to estimate the full state of the vehicle at a high rate (e.g., at 200 Hz). As discussed above, state estimation module 220 may include UKF 224 for this purpose. In the disclosed embodiments, an UKF is used instead of an extended Kalman filter (EKF) because of the desire to operate over a large operating envelope with significant excursions in roll and pitch angles from the hover configuration and relatively high velocities (e.g., up to 3 m/s). The state of micro aerial vehicle 100 is estimated by combining the 6-DOF pose from VIO system 222 with the measurements from IMU 234. In the model, the state is represented by the following:

x.sub.f=[x.sup.T v.sup.T .sup.T b.sub.a.sup.T].sup.T,(21)

where x and v have been defined above and the quaternion is represented by the following vector:

=[q.sub.0 q.sub.1 q.sub.2 q.sub.3].sup.T,(22)

and the accelerometer biases by the following:

b.sub.a=[b.sub.a.sub.x b.sub.a.sub.y b.sub.a.sub.z].sup.T.(23)

[0055] The prediction step uses the input linear acceleration and angular velocity measurements given by IMU 234:

u.sub.f=[.sup.T a.sup.T].sup.T, n=[n.sub..sup.T n.sub.a.sup.T n.sub.b.sup.T].sup.T, {dot over (x)}.sub.f=f(x.sub.f(t),u.sub.f(t),n),(24)

where n represents the process noise that we assume to be Gaussian white noise.

[0056] Finally, the pose estimates from VIO system 222 are used to update the state estimate. A linear measurement model is thus defined according to the following relationship:

z.sub.f(t)=Hx.sub.f(t)+,(25)

where is the observation noise, which is again assumed to be Gaussian white noise. The measurement model is linear since the update to the state estimate developed by UKF 224 is given by the absolute position and orientation of micro aerial vehicle 100.

[0057] In some embodiments, there can be a measurement delay where the rate at which VIO 222 is able to process images (e.g., at about 30 Hz) is different than a rate at which it is desired for state estimation and control to be updated (e.g., at about 200 Hz) to enable fast motions. With the present systems and methods, this delay is taken into account by buffering the values from IMU 234 until a new measurement from the algorithm of VIO system 222 is provided. Then, all the stored measurements from IMU 234 that are older than the current measurement in VIO system 222 are used as gain in the prediction step. The separation of VIO system 222 and UKF 234 is useful to keep the CPU usage limited. The state size of the VIO algorithm is not constant since image features are part of the state. For this reason, running it considering a prediction and updates steps at 200 Hz is more expensive than 30 Hz. In this way, we can have similar performances and we can satisfy the control rate constraints.

Experimental Results

[0058] In this section we report on demonstrations at the Consumer Electronic Show (CES) 2015 and experiments that have been performed in the GRASP Lab, at The University of Pennsylvania.

[0059] The prototype shown in FIG. 1A was exhibited in CES 2015 in Las Vegas during four consecutive days with over 200 demonstrations without failures. The demonstrations were conducted against a backdrop image of Las Vegas and consists of repeated vertical lines with only a few good features. In spite of this, the system performed successfully. In each demonstration, the user starts our app on the smartphone in the conventional way, which allowed the robot to take-off, hover, track preprogrammed trajectories in a 322 m.sup.3 space before landing safely. As discussed before, the app incorporates real-time estimation, control and planning.

[0060] The considered working area in the GRASP Lab, is a volume of 545 m.sup.3. A Vicon motion capture system, composed of 20 T040 cameras, provides a state estimate for micro aerial vehicle 100, which is considered ground truth in this context. Two sets of tests were conducted with multiple repetitions the first one considers the response of micro aerial vehicle 100 to step inputs. The second one is a trajectory tracking experiment to test the ability of the system to follow a trajectory in 3D space. In both experiments, the feedback control signal is obtained at 200 Hz from the state estimation approach discussed above. Results, including controller performance and a comparison of the estimation technique with respect to the Vicon motion capture system, show the precision of the estimation of the present approach during flight including the ability to handle fast motions. FIG. 5 illustrates a set of point clouds generated during a trajectory sample.

A. Step Response

[0061] The main purpose of this experiment is the evaluation of the controller performance in addition to the localization properties, which will be analyzed below. We propose to give three step inputs of 1 m along the three axes around at time instant 3 s, 13 s, 23 s respectively along z, x, and y axis as shown in FIGS. 6 and 7. The system employs an average of 1 s to reach the new desired value, which suggests a bandwidth of 0.25-0.5 Hz. The velocity changes accordingly on the three axes as shown in FIG. 7. It increases in the first part of the step signal and then it decreases to the 0 value such that the vehicle is able to keep the desired value in the Cartesian space. As illustrated in FIGS. 6 and 7, the estimation for position and velocity components is coherent with respect to the motion capture system, reaching velocities of 1.3 m/s. As shown in table I below, the Root Mean Square Errors (RMSE) and Standard Deviation (STD) with respect to the Vicon are reported. The average errors are 3 cm and 0.03 m/s for the position and velocity respectively, which are sufficient for autonomous navigation. Experimental results based on trajectory tracking are provided below.

TABLE-US-00001 TABLE I Position and Velocity RMSE and STD of the VIO and the UKF estimates compared to Vicon for the step response. RMSE VIO RMSE UKF STD STD STD Certesian estimation estimation Velocity position position velocity Component (m) (m) (m/s) VIO (m) UKF (m) (m/s) x 0.0171 0.0156 0.0598 0.0155 0.0138 0.0591 y 0.0253 0.0237 0.0608 0.0234 0.0221 0.0608 z 0.0293 0.0287 0.0357 0.0251 0.0236 0.0355

B. Autonomous Navigation and Planning

[0062] In this experiment, the system is set to follow a trajectory in 3D space to test the dynamic properties of the system. The results confirm the localization properties of the presented architecture and fully validate the proposed approach for autonomous navigation in an unknown environment. Since the input M is an algebraic function of the fourth derivative of the position (snap), it is convenient to plan smooth trajectories that minimize the snap of the trajectory using the following cost functional:

[00005]$\min .Math.{}_{t_0}^{t_f}.Math.{}_d.Math.{.Math.\frac{{}^4.Math.x_d\left(t\right)}{t^4}.Math.}^2.Math..Math.t,$

[0063] where .sub.d is a constant value and t.sub.0, t.sub.f are the initial and final time, respectively. This minimization problem can be formulated as a Quadratic Program (QP). Further, equality constraints can be enforced and can be determined by desired robot positions (or velocities). The trajectory that has been designed has the shape of two figure-8 patterns at different values of the z coordinate. In fact, as shown in FIG. 8, the first figure-8 pattern is executed at the altitude of 0.7 m, while the second one at 1.2 m. The transition between the two levels is done changing the height during the pattern execution without hovering before the transition. During the descent (See, e.g., FIGS. 9 and 11), the vehicle stops and hovers. The same procedure is used during the take-off operation (see the z component in FIG. 9 between 3 s and 10 s where the vehicle takes off, then hovers till it moves to the first 8 shape). This is produced to stress and test entirely the proposed localization and control system. In these situations, the vehicle is still able to localize and keep the control running. As shown in table II below, the values of the RMSE and STD are reported for the three axis components and for both VIO estimates and UKF estimates.

TABLE-US-00002 TABLE II Position and velocity RMSE and STD of the VIO estimation and of the UKF compared to Vicon at different speeds. Max. RMSE RMSE Velocity VIO UKF RMSE STD STD STD norm Cartesian estimation estimation Velocity position position velocity (m/s) Component (m) (m) (m/s) VIO (m) UKF (m) (m/s) 0.5 x 0.0265 0.0243 0.0486 0.0256 0.0230 0.0481 y 0.0277 0.0252 0.0611 0.0269 0.0243 0.0611 z 0.0255 0.0251 0.0258 0.0230 0.0230 0.0257 0.9 x 0.0339 0.0333 0.0485 0.0205 0.0182 0.0481 y 0.0326 0.0293 0.0623 0.0316 0.0283 0.0622 z 0.0306 0.0307 0.0307 0.0217 0.0215 0.0307 1.8 x 0.0238 0.0244 0.0786 0.0237 0.0244 0.0781 y 0.0336 0.0304 0.0632 0.0334 0.0302 0.0632 z 0.0278 0.0283 0.0476 0.0263 0.0268 0.0475 2.3 x 0.0716 0.0702 0.1004 0.0562 0.0534 0.0997 y 0.0467 0.0499 0.1183 0.0450 0.0484 0.1181 z 0.0336 0.0348 0.0674 0.0323 0.0334 0.0662

[0064] It is noted that the filtering technique is able to keep the same values of the VIO algorithm, while increasing the rate of the localization useful for control purposes. Along the three axis the value of the errors and STD is quite similar, but the interesting aspect to notice is that the error does not fluctuate much by decreasing the trajectory time and consequently having larger maximum velocities. This demonstrate the robustness of the estimation technique and the proposed framework for control and navigation with large excursion in position (see FIG. 9 between 12 s and 30 s) and velocities up to 2 m/s during the figure-8 shape execution (see FIG. 11). A slight increase in error is apparent for the test of 2.3 m/s, but the order of magnitude is the same with respect to lower velocities. In the fastest test, the system reaches roll and pitches angles close to 30, which causes image features to be lost and quickly re-estimated. Here as well, the system is stable and able to complete the overall task. The orientation error is evaluated as follows:

[00006]$\left(R,R_d\right)=\frac{1}{2}.Math.\mathrm{tr}\left(I-R_d^T.Math.R\right),$

where R is the vehicle's rotation and R.sub.d the desired one. As shown in table III below, the orientation RMSE and STD values with respect to the motion capture system are reported. They are small and of the same magnitude.

TABLE-US-00003 TABLE III Orientation RMSE and STD in radians of the VIO and the UKF estimates compared to Vicon. Max. Velocity RMSE VIO RMSE UKF Orientation norm (m/s) estimation estimation STD VIO STD UKF (R, R.sub.d) 0.5 1.7888 10.sup.4 9.3579 10.sup.5 1.2384 10.sup.4 5.9579 10.sup.5 0.9 2.5730 10.sup.4 1.5755 10.sup.4 2.009 10.sup.4 1.1557 10.sup.4 1.8 6.9388 10.sup.4 2.1319 10.sup.4 6.3921 10.sup.4 1.8506 10.sup.4 2.3 1.2 10.sup.3 3.2727 10.sup.4 1.1 10.sup.3 2.8741 10.sup.4

[0065] In addition, FIG. 10 illustrates the orientation error of the vehicle with respect to the motion capture system, VIO estimates, and UKF estimates.

[0066] In yet another aspect of the presently-disclosed subject matter, the concepts discussed above with respect to the present devices, systems, and methods may be applied to multiple micro aerial vehicles for operation together as a group (i.e., a swarm). This application of the present subject matter addresses three additional challenging problems for swarm of flying robots: environment mapping, autonomous navigation, and trajectory planning with multiple vehicles. In this context, it is desirable that, during the flight operations, inter-robots collision avoidance is guaranteed and that the system is agnostic with respect to interchangeability between robots. In addition, it is useful to have multiple MAVs simultaneously mapping an environment since they can collaborate in mapping tasks. The key benefits are twofold. The system is robust to single vehicle failures during the mission. Second, the environment can be covered and mapped in a faster and more reliable way than with a single vehicle. The fused map information can be exploited by every vehicle in order to make decisions, plan motions, and allocate tasks to vehicles.

[0067] Previous work has been performed on multi-robot systems focusing on MAVs. For example, it has been shown that two MAVs may map the same environment, with loop closure detection between different cameras, map merging, and concurrent map access being performed on interface device 250. In addition, a framework based on RGB-D sensors for cooperative localization and mapping has also been developed, wherein a monocular vision algorithm is used and the scale factor problem, due to the use of a single camera for localization, is solved using the depth data provided by the depth sensor. Other works use range sensors with ground robots in 2-D environments. Further, an interesting approach involves 3 synchronous cameras that are able to perform localization even considering dynamic environments. However, the images are required to be synchronized making the approach difficult to apply in the field of MAVs. All the previous works do not consider the benefits of an IMU measurement for absolute scale environment recovery, and they do not focus on the control and planning problems necessary to guarantee collision avoidance between vehicles. Conversely, other works consider the localization problems solved (this is mainly the case when an external motion capture system is used) and focus on the Concurrent Assignment and Planning of Trajectories (CAPT) with multiple vehicles. There are suboptimal approaches, which solve the CAPT problem using a centralized algorithm to create collision-free paths and solve the assignment problem for two-dimensional robots. In other approaches, centralized and decentralized solutions are presented for a N dimensional case. Other approaches analyze the scheduling and dynamic reallocation problems.

[0068] With the systems, devices, and methods discussed above for on-board sensing and control, however, a trajectory planning module is developed in which each robot is assigned to a goal location, and collision-free time parametrized trajectories are generated for multiple interchangeable vehicles. In this way, this is the first time that perception, planning, and control are combined for autonomous navigation of multiple interchangeable aerial vehicles without relying on GPS and on any external motion capture system, but just using COTS devices. To achieve this operation, some features of such a multi-vehicle system include the ability to generate time parametrized trajectories for quadrotors compatible with real time perception systems and the distribution of most of the computation load onboard each vehicle guaranteeing, at the same time, inter-vehicles collision avoidance.

Multi Vehicle Trajectory Planning

[0069] The main task of trajectory planning is, once a set of goals has been chosen, to generate trajectories that safely drive the vehicles to their corresponding locations without colliding between each other. This problem is called goal assignment and trajectories planning. Two versions of the algorithm, centralized and decentralized, have been proposed. In our case, we are interested in the centralized solution since it gives a complete solution to the problem.

A. The CAPT Problem

[0070] Let us consider N robots with radius R navigating from initial locations to M desired goal locations and suppose that the convex hull formed by the initial locations and goal locations is an obstacle free environment. The set of robots' locations and goal locations can be defined as

X(t)=[x.sub.1(t).sup.T, . . . ,x.sub.N(t).sup.T].sup.T,

G=[g.sub.1.sup.T, . . . ,g.sub.M.sup.T].sup.T(26)

[0071] It is possible to define an assignment matrix .sup.NM, which reveals for each robot the corresponding goal location. In particular, the generic element i, j in the matrix is 1 just if robot i is assigned to goal j. Clearly, the requirement is that every robot has an assigned goal which results in the following constraints:

.sup.T=I if NM,

.sup.T=I if M<N(27)

[0072] These constraints guarantee that each robot is assigned to a unique location in case MN and that there is a unique location assigned to each robot in case NM. The problem is to find trajectories for our vehicles X(t) such that for the initial time t.sub.0 and the final time t.sub.f, the following constraints hold:

X(t.sub.0)=[x.sub.1(t.sub.0).sup.T, . . . ,x.sub.N(t.sub.0).sup.T].sup.T,

.sup.TX(t.sub.f)=G if NM,

x(t)=G if M<N(28)

[0073] In addition, a minimum distance (t)>0 may be assigned between the two centers of mass of any pair of robots during the entire trajectory:

(t)=inf.sub.ijx.sub.i(t)x.sub.j(t)2Rt[t.sub.0,t.sub.f](29)

[0074] The goal is to find an optimal trajectory X(t)* and * such that the sum of the following cost function is minimized:

[00007]$\begin{array}{cc}\min .Math.{}_{t_0}^{t_f}.Math.{.Math.\frac{X\left(t\right)}{t}.Math.}^2.Math..Math.t,& \left(30\right)\end{array}$

[0075] subject to Equations (27), (28), and (29)

In the original problem, first order dynamics were considered and the solution consists of straight line trajectories, which satisfy the boundary conditions while minimizing the sum of distance traveled squared. This problem is solved decomposing it in two phases, the assignment phase and the trajectory generation phase. In the first one, the Hungarian algorithm is employed to identify the association to a goal for each robot, while in the second one the trajectory is generated. The Hungarian algorithm finds the following optimal assignment solution:

*=arg min .sub.i=1.sup.N.sub.j=1.sup.M.sub.i,jx.sub.i(t.sub.0)g.sub.j.sup.2,(31)

where .sub.i,j indicates the elements in the assignment matrix at position i. j. Once the assignment problem is solved, the final trajectory solution is given by:

X(t)=(1a(t))X(t.sub.0)+(t)(G+(I.sup.T))X(t.sub.0),(32)

with

(t)=.sub.i=0.sup.kc.sub.it.sup.i with (t.sub.0)=0 and (t.sub.f)=1.

If the initial and final separations are greater than 2{square root over (2)}R, trajectories will satisfy all the constraints and they are guaranteed to be collision-free. In this work, we are interested to fly all the quadrotors at the same time so a goal location needs to be assigned to every robot N=M.

B. The CAPT Solution for a Team of Quadrotors

[0076] The previous solution gives a useful result, which can be used to plan trajectories for a team of quadrotors. Considering Equation (1), it is observed that the nominal force can be determined from the acceleration of the trajectory:

=m{umlaut over (x)}+ge.sub.3,(33)

and the orientation of the third axis of body frame, b.sub.3 is:

[00008]$\begin{array}{cc}{b}_3=\frac{\stackrel{\mathrm{.Math.}}{x}+{\mathrm{ge}}_3}{.Math.\stackrel{\mathrm{.Math.}}{x}+{\mathrm{ge}}_3.Math.}.& \left(34\right)\end{array}$

Deriving Equation (1) again, the following relationship is obtained:

mx.sup.(3)={dot over (R)}e.sub.3Re.sub.3R{circumflex over ()}.sub.3{dot over ()}b.sub.3,(35)

and the scalar projection onto b.sub.3 reveals that

{dot over ()}=b.sub.3.Math.mx.sup.(3).(36)

Next, the first two terms of can be determined by solving Equation (35) for e.sub.3 and independently projecting onto e.sub.2 and e.sub.1 (note that R.sup.Tb.sub.i=e.sub.i and, similarly, e.sub.i.sup.TR.sup.T=b.sub.i.sup.T),

[00009]$\begin{array}{cc}\left[\begin{array}{c}{}_1\\ {}_2\end{array}\right]=\frac{m}{}\left[\begin{array}{c}-b_2^T\\ b_1^T\end{array}\right].Math.x^{\left(3\right)}.& \left(37\right)\end{array}$

The third term of is constrained by , the derivative of the yaw angle, one of the four flat outputs. Consider:

[00010]$\begin{array}{cc}{}^W=\left[\begin{array}{c}-\\ \stackrel{\_}{\stackrel{.}{}}\end{array}\right]=R.Math..Math.,& \left(38\right)\end{array}$

where .sup.W is the angular velocity of the body expressed in the world frame. Then, .sub.3 can be determined using e.sub.3.sup.TR:

[00011]$\begin{array}{cc}{}_3=\frac{\stackrel{.}{}-e_3^T\left(b_1.Math.{}_1+b_2.Math.{}_2\right)}{e_3^T.Math.b_3}.& \left(39\right)\end{array}$

[0077] The Equations (37), (39) show that angular velocity is directly related to the jerk (third order derivative of the position). Vision based localization systems are generally sensitive to fast rotations. For this reason, in case of team of quadrotors, it is of our interest when planning to minimize the following cost function:

[00012]$\begin{array}{cc}\min .Math.{}_{t_0}^{t_f}.Math.{.Math.\frac{{}^3.Math.X\left(t\right)}{t^3}.Math.}^2.Math..Math.t,& \left(40\right)\end{array}$

[0078] subject to Equations (27), (28), and (29).

Considering the fifth order polynomial trajectories, the corresponding path for each vehicle is given by:

p.sub.j(t)=.sub.i=0.sup.5c.sub.it.sup.ij[1, . . . ,N].(41)

The solutions are the trajectories that minimize the jerk along the straight line trajectories from the initial position to the goal location for each robot. Moreover, let us relax the constraint expressed by Equation (27) and consider homogeneous boundary conditions for velocity, acceleration, and jerk. Thus, the straight line can be parametrized as:

X(t)=(1(t))X(t.sub.0)+(t)X(t.sub.f),(42)

with

(t)=.sub.i=0.sup.5c.sub.it.sup.i with (t.sub.0)=0 and (t.sub.f)=1.

[0079] The homogeneous boundary conditions imply that the integral of the jerk squared is a constant factor times the integral of the velocity. This implies that the solution of the optimization problem Equation (42) is equivalent to the solve the optimization problem expressed by Equation (30). The solution given by Equation (42) is then a solution of the previous CAPT problem. It guarantees intra-robots obstacle avoidance during the flight. It is just worth to notice that the solution given by Equation (42) is equivalent to Equation (32) for N=M. In this case, it is then possible to decouple the assignment problem from the trajectory generation one. The final time can be chosen as:

[00013]$t_f={\max }_i.Math.\left(\frac{.Math.x_i\left(t_0\right)-{}_i^{{*}^T}.Math.G^T.Math.}{v_{\max }}\right),$

[0080] where v.sub.max is the maximum velocity that the user can choose and .sub.i* is the ith row of the optimal assignment matrix.

C. Semi-Distributed Algorithm

[0081] The main challenge in the presented system architecture, is related to its dependence on wireless communication to execute the trajectories since the algorithm is centralized. It is complicated and often too risky to send trajectories at 200 Hz over the network. Delays in the network infrastructure may affect the closed loop control and can produce collisions between the vehicles. To avoid the stream of the entire trajectory from interface device 250, only the coefficients obtained as a solution of the previous optimization problem are sent in separate threads to each platform. This strategy allows for the safe generation of trajectories without explicitly relying on network capabilities. The 6 c.sub.i coefficients of Equation (42) in addition to the starting and goal locations, expressed in the local frame of the single robot (the reference frame for estimation and control of every single robot), are sent via wifi through the UDP protocol to each robot.

[0082] The trajectories are then generated on-board of each vehicle in a separate thread such to guarantee real-time reliability. Once the trajectories are generated, a message is sent to interface device 250 from each vehicle and a trigger guarantees to start all of them at the same time. In this context, the only reasonable assumption is that all the phones have the same clocks.

Map Merging

[0083] The planning procedure has been previously introduced with the implicit assumption that the pose of all the vehicles is perfectly known. This is true since each vehicle has its own estimation framework as mentioned above. However, due to incremental pose estimation errors, the vehicle's pose can be prone to drifts. This behavior is particularly problematic in large environments and it can affect the assignment and planning because they are based on the pose information provided by each robot. Therefore, a new estimate of the vehicle's poses needs to be periodically computed to have a consistent planning algorithm. In addition, it would be desirable to obtain a unified representation of the environment and the single maps provided by each vehicle need to be merged.

[0084] As discussed above, each vehicle is able to generate a sparse point cloud. The feature points extracted in the environment, after a given number of measurements, are triangulated and inserted into the filter's state. Then, the 3D points are available to be used for environment reconstruction. The challenge is to enable the merging of multiple maps at the same time. In one embodiment, a set of keyframes is established on each robot and a set of SIFT descriptors is computed only for those keyframes. A predefined number of potential matching keyframe candidates between a vehicle and the common database has to be collected. A keyframe is selected if the distance of the new frame relative to all keyframes exceeds a threshold of the average scene depth. Interface device 250 implements a bag-of-word approach and when a sufficient overlap is detected between two potential keyframes, a relative transformation between is computed. The average keyframe processing time on interface device 250 is 30 ms. The descriptors are used for place recognition and the local features 3D points are used to solve a PnP problem between the overlapped keyframes. Especially useful in large environments, interface device 250 can run a full pose graph optimization thread. A pose graph optimization is preferable in this context to a full bundle adjustment since the last one is computationally demanding and may fail completely due to convergence into local minima.

[0085] We experimentally verified that every single map presents an average standard deviation with respect to a reference position of 5 cm at different distances ranging from 1 m to 10 m with very few outliers. These results show the possibility to obtain an accurate environment reconstruction just knowing the relative pose between the vehicles. It is worth noting that the presented strategy does not have strict computational requirements since interface device 250 is not involved in controlling the vehicles.

[0086] Finally, once a new pose estimate is obtained, the goal location of a robot can be corrected to guarantee that the conditions that guarantee inter-robots collision avoidance are still verified. This strategy has the additional benefit that the on-board maps and estimation pipelines do not need to be modified.

Multi-Vehicle Experimental Results

[0087] In this section, we report on the experiments that have been performed at The University of Pennsylvania with 3 quadrotor platforms. To show the performance of the presented approach, the lobby of a building (Levine Hall) is chosen to represent a neutral environment that is different from a laboratory. The considered working area is a volume of 1068 m.sup.3. The entire system running on the ground station (i.e., interface device 250) has been implemented in ROS and allows, as previously mentioned, the interaction with an user and the goal selection for every vehicle. The on-board phone system runs an android app.

A. Navigation of Three Quadrotors

[0088] Multiple sets of tests are used to show the performances of the proposed planning algorithm and architecture. During the flight, first, second, and third micro aerial vehicles 100a, 100b, and 100c are used to create a unified reconstruction of the environment and/or to generate specific shape configuration among first, second, and third micro aerial vehicles 100a, 100b, and 100c. In particular, it can be shown that flight with three vehicles can first generate linear motions (See, e.g., FIG. 12), then triangular shapes (See, e.g., FIG. 13), and then rotations (See, e.g., FIG. 14) in sequence.

[0089] As shown in the three cases, the vehicles are correctly assigned to the location minimizing the squared sum of all the distances in 3D space. The rectangular environment with black lines shown in FIGS. 12, 13, and 14 is illustrated to help a user to select the goal locations. The benefits of this strategy can be clearly noticed transitioning from the triangular shape motion (FIG. 13) to the rotation motion (FIG. 14). This confirms the correctness of the proposed approach and that the system is agnostic with respect to robots' interchangeability. Interface device 250 solves the assignment problem for 3 vehicles in 1-2 ms on a common i7 laptop. To plan trajectories at the take-off the initial position of the vehicles is assume to be known if no initial overlap is detected. It is a reasonable assumption to have an initial information since generally, when a mission starts, the vehicles' positions are known. It is worth specifying that the motions are generated continuously switching from one configuration to another. Each of them presents an average displacement of 2.5 m.

[0090] The proposed planning solution is also able to alleviate aerodynamic effects such to not impact the safety of the team. It can be enforced, considering a spherical model, that the center of mass of each pair of robots has to be at least n times the robot's radius R. This condition can be directly incorporated in the safety distance term between the center of masses expressed by Equation (29) and into the initial and final boundary conditions of the planning obtaining the same formulation. In the proposed experiments, we employ values n=5, 6. However, to further validate the proposed approach, the pipeline was also tested with two vehicles in hovering mode with the corresponding centers of mass at 1 m and 2.5 m from each other (the reader can notice that 1 m is lower than the minimum distance required by the algorithm to guarantee collision avoidance). We have experimentally verified flying autonomously, at different altitudes, that the standard deviation is less than 0.1 m as shown in table IV below. Moreover, once they are sufficiently far from each other the error is equivalent to the hovering one. Thus, the effects of disturbances are bounded and do not affect the safety of the team for n=5, 6.

TABLE-US-00004 TABLE IV Average mean error and standard deviation (STD) for different distance from the ground COM Ground distance (m) distance (m) Mean (m) STD (m) 1 1 0.0518 0.0420 0.2 0.0631 0.0438 2.5 1 0.0204 0.0239 0.2 0.0282 0.0252

[0091] In this way, micro aerial vehicles 100 are able to distinguish objects from a set of point clouds, validating the strategy discussed above. We can easily identify what points belongs to feature in the environment (e.g., stairs, boxes). In addition, experimental results show that different vehicles may contribute to different parts of the environment reconstruction, with the entire space being modeled colaboratively.

B. Extension to Larger Teams

[0092] It is worth noting the scalability of the proposed approach, increasing the number of elements in the team. The proposed architecture is semi-distributed, allowing it to easily increase the number of robots since the estimation, control, and planning pipeline running on each robot is the same. The key challenges for larger teams are twofold. First, the assignment and merging problems will take a longer time to be executed. Second, to fly hundreds of vehicles, due to space constraints, it is necessary to reduce the vehicles' size to maintain a compatible flight time. Regarding the first challenge, the assignment has cubic complexity and it can be solved in less than half second for hundreds of vehicles. For the map merging, it is very difficult to predict the exact time increase, since it dependents on many factors such as scene overlaps, the type and number of descriptors employed and the environment size. However, this task, as the assignment one, is solved on the ground station, not affecting the control and can be easily enforced before the planning.

[0093] In this work, it is shown that the hardware and software architecture with the underlying algorithms enable the plug and play functionality with a consumer product (e.g., a smartphone) and a quadrotor. The phone is able to solve real time control constraints, planning, mapping, and estimation tasks. In particular, it has been demonstrated that the autonomous navigation of a quadrotor platform is achieved using sensors onboard a smartphone, such as a single camera and an IMU. With data from an external motion capture system used to measure ground truth, it has been demonstrated that the robot can navigate in three dimensions at average speeds of 1.5-2 m/s with an average error of 3 cm in position. The use of these devices in robotics has great potential for STEM education and for personal robots.

[0094] In addition, such systems, devices, and methods may be applied to a multi-robot system with perception capabilities, enabling environment reconstruction and preserving collision avoidance between robots during the trajectory execution tasks. The system is based on single phones running an app and performing state estimation, environment reconstruction, and control in real-time using a phone camera and an IMU. The key components are identified in the estimation, planning, and map merging algorithms. The architecture guarantees, despite the centralized properties of the planning algorithm, reliance on wireless communication only for a fraction of the entire pipeline and on-board distribution of most of the demanding capabilities. The final reconstruction shows the possibility to identify different objects in the environment.

[0095] The present subject matter may be embodied in other forms without departure from the spirit and essential characteristics thereof. The embodiments described therefore are to be considered in all respects as illustrative and not restrictive. For example, as discussed above, although particular embodiments and implementations of the subject matter are disclosed, those of ordinary skill in the art will recognize that the concept of fully autonomous vehicles into which commercial off-the-shelf hand-held electronic products are integrated as the control and sensor suite can be implemented in any of a variety of additional embodiments. Accordingly, although the present subject matter has been described in terms of certain preferred embodiments, other embodiments that are apparent to those of ordinary skill in the art are also within the scope of the present subject matter.