University of Twente Student Theses
Efficient path planning for multiple agents in agriculture fields
Sinai, Lior (2020) Efficient path planning for multiple agents in agriculture fields.
This is the latest version of this item.
|
PDF
5MB |
| Abstract: | This report focuses on the particular task of path planning. This problem is NP-hard and is closely related to the vehicle routing problem (VRP) in operations research. Given a known map of an agriculture field, the goal is for the robots to allocate and visit all the targeted crops in an efficient way as a team. Here ’efficient’ means minimum distance and time, but it is shown that often both cannot be minimised simultaneously. In particular, using more agents results in a longer total distance but a shorter time overall. Instead a cost function was developed to balance these two metrics. Two environments were developed in Python. A continuous environment with a basic physics model without collisions, which is used to simulate aerial robots, and a grid environment with obstacles, which is used to simulate ground robots moving between crops. The obstacles were static, so Dijkstra’s algorithm was used to find the shortest paths around them. This meant the same algorithms could be used in both environments. Exact solutions were found with the Bellman-Held-Karp algorithm, but it runs in exponential time. The focus instead was on more practical approximation algorithms which run in polynomial time. These were: nearest neighbour (NN) ranked, dividing the field into clusters and then using the NN algorithm or Christofides’ algorithm, Ant Colony Optimisation (ACO) and Q-learning. Of these, ACO performed the best on the distance and time metrics. However the solution is partly random, which resulted in path crossing - which increases the chances of collisions between agents - and a large spread between the distances agents’ travel - which leads to uneven wear and tear. Clustering with NN or Christofides’ gave more controlled solutions with comparable metrics. |
| Item Type: | Essay (Master) |
| Faculty: | EEMCS: Electrical Engineering, Mathematics and Computer Science |
| Subject: | 02 science and culture in general, 31 mathematics, 48 agricultural science, 55 traffic technology, transport technology |
| Programme: | Systems and Control MSc (60359) |
| Link to this item: | https://purl.utwente.nl/essays/80763 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page