Error Correction for Drone flight path management

With the popularity of modular composition, many industries are taking advantage of a fleet of functional units that can collectively function as a whole and eliminate the risks of the monoliths that used to serve the purpose earlier. Fleet refers to many drones, bots or other software automations that are capable of a specific function such as moving from point A to point B in space. 

While single remote-controlled units can follow the handlers' commands in real-time, the fleet usually operates according to a program. Centralized logic maps an initial state to a final state and issues command to each drone to move from the starting point to the ending point. It is easy for software to map initial co-ordinates for each drone in a formation on land and command them to move to a final co-ordinate in the sky to form a specific arrangement. 

Autonomous drone fleet formation avoids the need for a centralized controller that plots determines the final co-ordinates and non-overlapping flight path for each unit. The suggestion is that the computation for the final position from the initial position for each unit does not need to be performed at the controller and that logic can be delegated to the autonomous units. For example, if we wanted to change a fleet forming the surface of a sphere to a concentric plane of Saturn-like rings, then the final co-ordinates of each unit must be distinct, and its determination is not restricted to processing at the controller. While autonomous decisions are made by individual drones, they must remain within the overall trajectory tolerance space for the entire fleet. This can be achieved with the popular neural net for softmax classification. The goodness of fit for a formation or sum of squares of errors of F-score are other alternative measures. This is not a one-time adjustment to the formation but a continuous feedback-loop circuit where the deviation is monitored, and suitable error corrections are performed. Correction can also be translated as optimization problems where the objective function is maximized. It is common to describe optimization problems in local versus global optimization. Local optimization involves finding the optimal solution for a specific region of the search space while global optimization involves finding the optimal solutions on problems  that contain local optima. In some cases, joint local and global optimization recommendations can be computed and applied. The choice of algorithms for local search include Nelder-Mead algorithm, BFGS algorithm, and Hill-Climbing algorithm.  Global optimization algorithms include Genetic algorithm, Simulated Annealing, and Particle Swarm Optimization. The sum of square errors is almost independent of space-time variables and gives a quantitative measure that works well as the objective function to optimization problems. Therefore, the sum of the squares and the simulated annealing algorithm are good general-purpose choices that are applicable to drone formations. The formation is singleton otherwise the divisions can be treated like formations with cohesion and separation. The relationship between cohesion and separation is written as TSS = SSE + SSB where TSS is the total sum of squares. SSE is the sum of squared error and SSB is the between group sum of squares, the higher the total SSB, the more separated the formations are. Minimizing SSE (cohesion) automatically results in maximizing SSB (separation). Formation can be ranked and processed based a Silhouette co-efficient that combines both cohesion and separation.  This is done in three steps. 

For the I'th object, calculate its average distance to all other objects in formation and call it ai 

For the I'th object, and any formation not containing the object, calculate the object's average distance to all the objects in the given formation. Use the minimum value and call it bi 

For the I'th object, the silhouette coefficient is given by (bi-ai)/max (ai, bi)

Sample python implementation: 

#! /usr/bin/python 

def determining_replacement_for_team(nodes): 

                              Return formation_centroids_of_top_formations(nodes) 

 

def batch_formation_repeated_pass(team, nodes) 

                    team_formation = classify(team, nodes) 

                    proposals = gen_proposals(team_formation) 

                    formations = [(FULL, team_formation)] 

                     For proposal in proposals: 

                                             Formation = get_formation_proposal(proposal, team, nodes) 

                                              formations += [(proposal, formation)] 

                     Selections = select_top_formations(formations) 

                     Return team_from(selections) 

 

Def select_top_formations(threshold, formations, strategy = goodness_of_fit): 

                     return formations_greater_than_goodness_of_fit_weighted_size(threshold, formations)

def annealingoptimize(domain,costf,T=10000.0,cool=0.95,step=1): 

     # Initialize the values randomly 

     vec=[float(random.randint(domain[i][0],domain[i][1])) 

          for i in range(len(domain))] 

     while T>0.1: 

          # Choose one of the indices 

          i=random.randint(0,len(domain)-1) 

          # Choose a direction to change it 

          dir=random.randint(-step,step) 

          # Create a new list with one of the values changed 

          vecb=vec[:] 

          vecb[i]+=dir 

          if vecb[i]<domain[i][0]: vecb[i]=domain[i][0] 

          elif vecb[i]>domain[i][1]: vecb[i]=domain[i][1] 

          # Calculate the current cost and the new cost 

          ea=costf(vec) 

          eb=costf(vecb) 

          p=pow(math.e,(-eb-ea)/T) 

          # Is it better, or does it make the probability 

          # cutoff? 

          if(eb<ea or random.random( )<p): 

               vec=vecb 

          # Decrease the temperature 

          T=T*cool 

     return vec 

#codingexercise

Given a sorted integer array nums and an integer n, add/patch elements to the array such that any number in the range [1, n] inclusive can be formed by the sum of some elements in the array.

Return the minimum number of patches required.

class Solution {

    public int minPatches(int[] nums, int n) {

        int count = 0;

        int[] sums = new int[n+1]; 

        Arrays.fill(sums, 0);

        sums[0] = 1;

        List<Integer> elements = new ArrayList<>(nums);

        while(!allOnes(sums)){

            List<List<Integer>> combinations = new ArrayList<>();

            List<Integer> selection = new ArrayList<Integer>();

            combine(elements, selection, 0, 0, combinations);

            for (int i = 0; i < combinations.size(); i++) {

                int sum = combinations.get(i).stream().sum();

                if (sum <= n && sums[sum] != 1) {

                    sums[sum] = 1; 

                } 

            }

            addLowestMissingNumber(elements);

            count++;

        }

        return count;

    }

}