Best algorithm for an object that moves across an area

[cashflow]

Imagine a rectangular plane with dimensions X and Y. On that plane is a car. The car is about Z meters wide (the front bumper width, or up-down width in the image below). The car travels at a velocity v and moves across the entire surface as shown below:



The car in the image above can move left-right or up-down or diagonal or whatever. The car takes T seconds to make a 90 degree turn. The car will need to move across every square inch of the area in the fastest possible time.

I'm trying to come up with an algorithm (perhaps a regression model) to prove the fastest possible time for this car to transverse the entire surface area. I thought that going left-right will be fastest, since the car will take t*2 seconds to make the 180 degree rotation once per row. Going up-down just adds more turns, and I'm not even sure about diagonal movements or moving around the perimeter etc. How would I tackle this problem (ignoring friction, internal resistance, etc, but I'll need to come back to that later)?

(This is not a homework question, I'm working on a project where I need to move an object across the area in the fastest possible time.)

 

[Simon Bridge]

From that description: looks like you need to minimize the number of 90deg turns.

 

[eigenperson]

Your method is minimal, though not uniquely so.

(Almost) proof:

Without loss of generality you can view the board as a rectangular m-by-n chessboard (m ≤ n) and the car as a rook that has to cover every square in the minimum number of moves (I am making some very minor simplifying assumptions here). The algorithm you suggested covers every square in 2m-1 moves; assume for purposes of contradiction that there is a shorter optimal algorithm. Clearly horizontal and vertical moves must alternate in any optimal solution, so there are at most m-1 vertical moves in the shorter optimal solution. (If there were m vertical moves then there would be m-1 horizontal moves in between them, which totals to 2m-1, contradicting the assumption that the optimal algorithm is faster than 2m-1 moves.)

Each vertical move visits at most one square in each row, and therefore the vertical moves can't eliminate all the squares from any row, since there are n > m-1 squares in each row. This means there is at least one square left in each row that requires a horizontal move along that row to eliminate. There are m rows, so this is m horizontal moves. There must therefore be at least m-1 vertical moves and m horizontal moves, for a total of 2m-1. This contradicts the assumption that there was a shorter optimal algorithm.


So basically you can do it in no fewer than 2m-1 moves (2m-2 turns), where m is the shorter dimension of the region as measured in car-widths. But there is more than one way to achieve that minimum.

 

[cashflow]

There must therefore be at least m-1 vertical moves and m horizontal moves, for a total of 2m-1.

Oh I see. This helps a lot, thank you!

Just a thought... Let's say you go around the perimeter, from the outside to the inside. You will end up with the same number of moves, but each time you are making a 90 degree rotation instead of a 180 degree U-turn. This seems to be faster than going row by row, since making a 180 degree U-turn is t*2.

 

[Simon Bridge]

You thinking of going in a spiral?
t*2=2t ... i.e. the time it takes to make two 90deg turns. The "180deg turn" is a 90deg turn followed by a move 1 space followed by another 90 deg turn.

Spiraling in from the outside, you still get two 90deg turns on each row except the top one.

IRL: a hairpin 180 like that would probably take longer than two 90deg turns separated by a straight... bootlegging it would be possible but that involves coming to a dead stop. Acceleration/decelleration has not been included in the model though.

 

[eigenperson]

Just a thought... Let's say you go around the perimeter, from the outside to the inside. You will end up with the same number of moves, but each time you are making a 90 degree rotation instead of a 180 degree U-turn. This seems to be faster than going row by row, since making a 180 degree U-turn is t*2.

I don't think you're counting the turns right.

If you make a genuine 180-degree turn, you end up retracing your steps. So this is always a poor strategy.

What you actually do in the "back and forth" algorithm is to go forth across the entire area, turn 90 degrees, go a very short distance (1 car width), turn 90 degrees, and go back across the whole area.

So you end up making the same number of turns either way, and all of them are 90°. You also travel the same distance either way. So they take the same time.

 

[jbriggs444]

The car in the image above can move left-right or up-down or diagonal or whatever. The car takes T seconds to make a 90 degree turn. The car will need to move across every square inch of the area in the fastest possible time.

So, in particular, the car need not do a "rook's tour". It could, for instance, turn while moving,
following a curving path without slowing down as long as the instantaneous turning radius is always less than r = 4Tv/pi

One could imagine a tour that follows a prolate cycloid path with excursions outside the intended coverage area.

This sounds a lot like crop dusting.

 

[cashflow]

Yes, the object can move in any direction. It moves very slowly in the Z direction however (where Z is up). How did you end up with the "r = 4Tv/pi"?

 

[Simon Bridge]

You never said how long it took to turn to angles other than 90deg.
Note: the original statement has the car only able to turn 90 deg but apparently capable of moving diagonally without changing direction. technically you don't state that the car needs to turn to go up and down either ... but that seemed like a safe assumption.

It could make matters clearer if you state the car motion in car terms rather than ground terms.
i.e. the car can go forwards and backwards, and it can turn. The turn rate is...

If traveling outside the designated area is possible, then you may get solutions similar to the old "join the dots" puzzle. Then there are weird-topology variations... i.e. if the plane in question is on a cylindrical surface, then you could cover all the space without turning (by running over them diagonally).

 

[cashflow]

Thanks everyone for your help thus far.

Traveling outside the designated area is indeed possible. The plane is rectangular. The turning is linear-- every 90 degrees takes t seconds. So turning 45 degrees would take t / 2 seconds etc. The turning is already relative to the car-- the car turns 90/t degrees per sec.

So right now, either going by rows or going around in a spiral seems to be the fastest approach (both take the same number of turns). Now, what if we add obstacles, like so? The rectangle inside has lengths k by l, and the circle is of radius r. I still think that the same algorithm could be used, the car could just go around it without losing too much time. Not sure if there's a better way.