Autonomous drone formation morphing: 

Drone  formations are easier to make when there is a single controller and aided by cameras and GPS coordinates. But it requires connectivity to all the drones. If this can be pulled through, drone formation can be storyboarded. It’s during this step that the displayed shapes, music and synchronization are worked out, whether it’s a movie logo, marriage proposal or giant internet meme.  

One of the ways drone formations can autonomously converge to a final shape is by determining the position of each drone in the final shape starting from an overall cube on whose surface are the initial positions. Each drone can then find the shortest non-intersecting path from the initial position to the final position. A cube is preferred to a starting 2D matrix formation because it provides the ability to converge quickly. Drones are limited by their battery power and weight which usually results in formation timespan of fifteen minutes on average.  

We choose a specific scenario for a problem statement to this purpose. Given a fleet of drones on the surface of a cube, the fleet must converge to a sphere of a certain radius from a given center within the cube. If a plane is given to cut through the center, the fleet must converge to Saturn-like rings around the center. These are illustrated with images as shown below: 

 

One way to do this would be to converge or diverge from the initial position for each drone independently of the others by plotting paths that are independent of one another. For example, the following diagram illustrates how an arbitrary shape can be etched by drones levitating to different heights along parallel independent verticals corresponding to each cell on the surface of a grid, to plot the final shape  

Collapsing on to a 2D plane from a 3D object such as for concentric circles is easier with the projections on to that surface. For example, projections of a circle to a plane inclined at 30 degrees to the vertical can be viewed as: 

 

Morphing or blending algorithms begin by constructing a common connectivity for two or more geometries at hand. Then they proceed to linearly interpolate the geometry to generate intermediate models. The improvements can be made iteratively until there is none possible.  

The Zobrist hashing can be used to determine if there were any changes between two intermediary stages and if there are none, then the final solution is reached. 

With the example of a matrix of integers with cell values ranging from 1 to 2000, two arrangements of the matrix might be different, if they give different hashes when computed as follows: 

    private int[][] zobristInit(int[][] board) { 

        Random rn = new Random(); 

        int[][] randoms = new int[board.length * board[0].length][2001]; 

        for (int i = 0; i < randoms.length; i++){ 

            for (int j = 0; j < randoms[i].length; j++) { 

                randoms[i][j] = Math.abs(rn.nextInt()); 

            } 

        } 

        return randoms; 

    } 

 

    private int zobristHash(int[][] randoms, int[][] board){ 

        int h = 0; 

        for (int i = 0; i < board.length; i++) { 

            for (int j = 0; j < board[i].length; j++) { 

                h = h ^ randoms[i * board[0].length + j][board[i][j] % 2001]; 

            } 

        } 

 

        return h; 

    } 

And the hash could be used to continuous improve the adjustments to the fleet formation with an example as: 

    public int[][] morph(int[][] board) { 

        var randoms = zobristInit(board); 

        int hash = zobristHash(randoms, board); 

        int previous = Integer.MIN_VALUE; 

        while (previous != hash) { 

            previous = hash; 

            int[][] reduced = adjust(board); 

            board = dropVerticallyOverIndependentVerticals(reduced); 

            hash = zobristHash(randoms, board);         

         } 

        return board; 

    } 

Thus, determining initial and final positions and non-overlapping paths between those positions is sufficient to transform from an initial formation to a final one.