3
$\begingroup$

I have a problem that is similar to this that I am trying to solve: "Given a randomly-shaped field, what is the best (fastest I guess) way to plow it? Every part of the field must be plowed, plowing outside the area is not a problem, and turning around is slower than going straight."
Basically, I'm in the situation of a farmer that wants to plow as fast as possible a weirdly-shaped field with no obstacle.

As far as I can tell, this is a covering problem for a simply-connected 2D space, but with some special restrictions.

It seems like it should be a common enough problem, but I can't seem to be able to find anything. I guess most fields have a shape similar enough to a rectangle and thus it is not an issue.
Is there any algorithm or numerical method that allows to solve this problem?

Thanks.

$\endgroup$
  • $\begingroup$ If you model your polygonal area as a solid grid graph (and don't consider the additional cost of turns), then the problem of finding an Hamiltonian cycle is solvable in polynomial time (see W. Lenhart and C. Umans, “Hamiltonian cycles in solid grid graphs,” in Proc. of the 38th Annual Symposium... (FOCS '97), pp.496–505, 1997) while the complexity of finding an Hamiltonian path (on solid grid graphs) is still open (up to my knowldge). Both problems are NP-complete on grid graphs (and also your problem is NP-complete if some parts of the field cannot be plowed or have already been plowed). $\endgroup$ – Vor Jan 26 '16 at 19:44
  • $\begingroup$ I do have to consider the costs of turns though. But thanks. $\endgroup$ – Leherenn Jan 27 '16 at 7:58
0
$\begingroup$

Even for a near rectangular field, plowing along the long sides should be more efficient than along the short ones, but the solution isn't trivial I think. When the field slightly deviates from being perfectly rectangular, naive plowing will leave you with a triangular patch that will require a lot of turning to finish.

We could observing that all furrows need to be parallel, both in practice as well as from an optimization perspective. Then a mathematical description of the problem would be that you have a set of evenly spaced parallel lines in the plane and you want to fit (i.e. rotate and translate) the polygon so that the number of intersections between it and the lines is minimized. Note that there are infinitely many infinitely long lines in this description, think drawing the polygon on lined paper.

I don't see a quick archetypal problem for this myself, but I think you could try brute-forcing it by rotating the polygon over the lines and computing the lines-polygon intersections at each turn.

$\endgroup$
  • $\begingroup$ Do the furrows really have to be parallel? If the field is a disc, wouldn't it make more sense to spiral towards the center, and then finish the inside with a couple of parallel plows? Thinking of it, a rounded rectangle could probably be plowed perfectly that way. $\endgroup$ – Leherenn Oct 28 '15 at 12:27
  • $\begingroup$ Well, it'd depend on the abstraction you think is suitable. From my assumptions the model I explained seems reasonable and provides a workable mathematical setting to investigate the problem. The spiral model might also work out, but I think that you'd lose your gain when you consider the leftover corners, particularly for concave polygons. $\endgroup$ – Fasermaler Oct 28 '15 at 13:42
2
$\begingroup$

You'll find plenty of literature on this widely-studied problem, which is called complete coverage path planning. Many techniques have been applied with more or less success (genetic algorithms, etc.) but in the end the only viable technique is some variant/improvement on the boustrophedon decomposition algorithm, which is in the class of Morse decompositions.

Choset's paper is the founding document, but I found Xin Yu's PHD dissertation to be the best practical description. The problem is that Boustrophedon decompositions find only a single 'best' ploughing angle for all trapezoids, when some may certainly be better ploughed at some other angle.

Bochkarev and Smith recently described a way to minimize turns by exploiting the minimum altitudes of the polygons, but I found it difficult to grasp with my limited high-school maths.

I am currrently trying out an alternative approach, by taking a Boustrophedon decomposition at all the angles of the polygon and then layering all the resultant trapezoids sorted by a score based on area and minimum altitude. If it works out I'll try and remember to come back here to post the results.

Citations

Choset, Howie. "Coverage of Known Spaces: The Boustrophedon Cellular Dercomposition" Autonomous Robots 9, 247-253, 2000.

Xin, Yu. "Optimization Approaches for a Dubins Vehicle in Coverage Planning problem and Traveling Salesman Problems" PhD Dissertation, Auburn, Alabama, 2015.

Bochkarev, Stanislav and Smith, Stephen L. "On Minimizing Turns in Robot Coverage Path Planning" Automation Science and Engineering, 2016

$\endgroup$
  • $\begingroup$ Welcome to the site! It would be helpful if you could give full citations to the papers you link since links to people's websites can quite often break (especially when an academic moves to a different job. Thanks! $\endgroup$ – David Richerby Dec 1 '16 at 13:30
  • $\begingroup$ You're quite right, I know and I would willingly. The problem is that the 'official' versions of those papers are invariably behind paywalls, so I figured better a link that people could reach. What I could do is give the full title, if that would help? $\endgroup$ – smirkingman Dec 1 '16 at 14:17
  • $\begingroup$ The title would definitely help, yes. Note that giving a full citation doesn't mean you can't link the free PDFs on the authors' sites. $\endgroup$ – David Richerby Dec 1 '16 at 15:08

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.