Summary
We recognised the problem to be a travelling salesman problem, because there are a massive number of possible drop-off and pick-up points for each debris and different possible permutations of the debris. Thus, we could create a series of nested for loops that check every possible permutation and drop-off and pick-up points to a six-decimal point precision (the max precision the ZeroRobotics IDE will allow) that would result in a massive number of iterations that could be unrealistic to calculate.
Initially, we created functions that find the most optimal drop off and pick up point between two debris. However, because these two functions find the most optimal drop off and pickup points only considering two debris, it may not minimise the overall cost. Thus, in order to find points that are more cost efficient and realistic to calculate, we used the functions to find drop-off and pick-up points for each debris and manually adjusted the points so that, 1. they were moved in the direction of the next object, 2. increased the overall battery score and time score range. For pick up points, we used Desmos Graphing Calculator to graph circles with the centres of the debris and radius of the maximum distance one can pick an object at from to locate possible pick-up points to test.
We avoided the gap between objects 0, 3 by using permutations that did not involve travelling between the 0-3 gap, e.g. for positions 3, we retrieved object 3 first, then moved in a counterclockwise direction from object 2 to object 0, because more debris are located along the other edges.
Written by Charlotte
Created a function that returns the most optimal pick-up point between two debris
1. Contains a for loop that runs 200,362 times and finds the pick-up point with the least cost
2. See the screenshot of the code below ⬇️⬇️⬇️⬇️⬇️⬇️⬇️⬇️
Code written by Jacob
2. Utilized a recursive binary search algorithm to find the most cost-efficient drop-off point between two debris (see code skeleton and screenshots of code below)
Code written by Charlotte
The algorithm takes the range which to search within (depending on the nearest edge) between x or y coordinates of the centers, sets one limit to the high and the other limit to the low, then compares which limit results in a lower cost. It then splits the range in half and continues to search the range with new limits of the average of the previous two limits and the limit with the lower cost.
see code skeleton below for function prototypes of finding the nearest edge to drop off at and the function for calculating the drop-off point
see screenshots of the code below
Left is the code skeleton for the drop-off point algorithm
Left is the code for the drop-off point algorithm