2
$\begingroup$

I need to generate the shortest possible path for aerial photography using a fixed wing unmanned air vehicle (UAV).

The image below shows the area I'm going to search. The white cells are the cells I want to photograph (must be traversed), and the black tiles are not of interest (doesn't have to be traversed). The middle of each cell is a waypoint/node.

Because the camera view banks when the UAV changes direction, the cost of turning inside the white area is more costly than turning inside the black area.

I have looked at different graph search algorithm like A*, Dijkstras, etc, but I'm unsure how they can be applied.

I'd appreciate any pointers that could help me solve this problem.

enter image description here

$\endgroup$
  • $\begingroup$ Do you have starting and ending point? How costly is turning back? (How many pieces it takes? ) is it allowed at all or uav can onlu turn after picture is taken on white cell, going through black cells or you need only to minimize number of turns on white cells, not overflowing? (As I understand the overall length is also considered somehow?). $\endgroup$ – Evil Apr 17 '18 at 18:50
  • $\begingroup$ Have you tried looking at algorithms for Hamiltonian path and the Euclidean Travelling Salesman Problem? $\endgroup$ – D.W. Apr 17 '18 at 22:20
  • $\begingroup$ Something like this seems very close to your needs. $\endgroup$ – Evil Apr 18 '18 at 0:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.