little math problem October 2018

[pier4r]

Sharing the question from "fermat's library" on twitter (n1) and rephrasing the context a bit.

On a planet, with a relatively friendly surface, two rovers are landed but they end in two different places (they cannot see each other directly). Communications between the rovers is impossible (unless they are in line of sight), and they are programmed to first find each other.

Which "find the other rover" strategy would you program in them and why? What is the expected time to find each other?
If you need a planet/celestial body as reference (for size not location), say the moon.





n1: social network, even after all the machine learning / ai hype, are still offering relatively dismal recommendations that fit one's niche interests. Therefore I use the occasion to suggest Fermat's library on Twitter. In general on Twitter I found better feeds than on FB. FB has more potential being more expressive (you know, thousands of characters in a post), but most of the groups/pages are inactive or private or even more difficult to find. Other SN are even worse, like youtube. On youtube with recommendations alone the hpcalc.org channel is impossible to find.

[Zaphod]

Quote:What is the expected time to find each other?

Without the size of the planet and the potential speed of the rovers the only answer to this can be:

Quote:Presently

[pier4r]

Yes and no. I was maybe not that precise (well the twitter is even shorter).

Let's say that you can work with upper bounds or the time needed, that are a function of the planet size. Like complexity. So you don't really need the planet size.

If you want set one, not a degenerate case though (like an asteroid). Say the moon.

[Thomas Okken]

I'm sure this isn't optimal, but just to get started:

The greatest distance at which the rovers can see each other is D. The radius of the planet is R. The rovers can travel at a maximum speed V.

Assumptions: the planet is a perfect sphere, no water, no hills. Visibility is the same everywhere.

One rover stays put, the other starts searching. It searches in an expanding spiral, where each circuit is 2 * D from the last. I'm ignoring the details of the shape of that spiral near its ends.

The rover covers an area of 2 * D * V per unit of time. The area of the planet is 4 * pi * R^2, so it takes a time (4 * pi * R^2) / (2 * D * V) to search the entire planet, and the expected search time is half that.

[Mark Hardman]

Strategy:

Both rovers move to the closest point on a pre-determined great circle--let's say the equator. One rover travels along the great circle following the rotation of the planet and the other travels against the rotation of the planet.

[sasa]

If both rovers are "blind", i.e. cannot locate it's position and communicate with eventually orbital module when visible, the fastest and dynamic way I can think of is that both go to one of designated magnetic pole.

That way both will not miss each other, both will move cutting searching time on half, saving energy... In worst case scenario, both together will cross less than D to the designated pole, with in less than (D/V)/2. The best case scenario, of course, is when both are close to the designated pole, when both will cross less than D/2 in less than (D/V)/4 time.

Indeed, some more details may result in better strategy...

[pier4r]

(10-20-2018 08:14 PM)Mark Hardman Wrote:  Strategy:

Both rovers move to the closest point on a pre-determined great circle--let's say the equator. One rover travels along the great circle following the rotation of the planet and the other travels against the rotation of the planet.

Nice idea. One possible problem. How do they now they got to some greater circle without having a sort of GPS ? We could assume they can use the information given a priory about the planet and then check the sun/stars to define their positions, although that is really close to say "let's say there is an orbiting module around the planet".

[Zaphod]

(10-20-2018 08:05 PM)Thomas Okken Wrote:  The rover covers an area of 2 * D * V per unit of time. The area of the planet is 4 * pi * R^2, so it takes a time (4 * pi * R^2) / (2 * D * V) to search the entire planet, and the expected search time is half that.

But that (making actual physical contact) would be (slightly) longer than actually getting visual sight of each other.

The diameter of the planet and the height of the visual scanning hardware (and the tallest part of the other rover) comes into play surely.

[brickviking]

In addition, there's nothing I can see that mandated that the planet even have a magnetosphere, let alone that you could view the sky. Those two factors alone could count out most current dead-reckoning (i.e. with a compass, astrolabe or sextant), and may only leave you with mapping (this is where I've been and what direction I turned) or surveying tools (we've measured this far in this direction) that don't depend upon a magnetic field.



(Post 309)

[Mark Hardman]

(10-20-2018 10:50 PM)brickviking Wrote:  In addition, there's nothing I can see that mandated that the planet even have a magnetosphere, let alone that you could view the sky. Those two factors alone could count out most current dead-reckoning (i.e. with a compass, astrolabe or sextant), and may only leave you with mapping (this is where I've been and what direction I turned) or surveying tools (we've measured this far in this direction) that don't depend upon a magnetic field.



(Post 309)

Then this problem is more about Schrödinger's rovers than navigation.

I maintain that celestial navigation would be sufficient for locating the planet's equator.

[Paul Dale]

This would be a problem for mission control not the landers. Since it is on the moon, life isn't too difficult. If mission control doesn't know where they are, they should be able to figure it out. If carried, retroreflectors would help for example. Failing that the Lunar Reconnaissance Orbiter ought to be able to image the landers directly. Then, tell the rovers where to meet

The moon doesn't have a magnetic field so a compass is useless. Finding the equator should be possible, although a little slow. Using the star field for navigation should also be workable. So either meet at a preset location or find the equator and drive.


Pauli

[sasa]

(10-20-2018 09:41 PM)pier4r Wrote:  We could assume they can use the information given a priory about the planet and then check the sun/stars to define their positions, although that is really close to say "let's say there is an orbiting module around the planet".

The original problem was about two friends left on a big sphere where communication is impossible and question was what is the fastest way to find each other... And that is not a math, but just a brain teaser type of puzzle...

Back to your modification... If there is no way to determine position (including navigation by stars), reference point and direction, this is simply "needle in a haystack" search (without a magnet). What only left is what Tomas wrote, assuming primary rover have unlimited energy, memory to map whole terrain and unlimited time...

Without some more missing details mentioned already, this kind of "brute force" solution only applies...

[Ken S]

If you had at least an understanding of where you have been relative to where you are it seems leaving one in place and driving twice the distance of your radio range from your beginning point then circling around your beginning point until you get to radio range of the start of the circle then step out twice your radio range again. But if you don't even have that much navigation it would be completely random.

[Dave Shaffer]

(10-20-2018 11:49 PM)Mark Hardman Wrote:  Then this problem is more about Schrödinger's rovers than navigation.

I maintain that celestial navigation would be sufficient for locating the planet's equator.

Not if you can't see the sky (cloud covered, like Venus) and the planet is not rotating (unlikely, but conceivable, and similar to Venus as well)

The statement of the problem in its broadest sense implies little if any a priori knowledge about conditions on the planet.

[Dave Shaffer]

(10-20-2018 06:48 PM)pier4r Wrote:  If you need a planet/celestial body as reference, say the moon.

Reference as in "a similar celestial body" or as in "something you can see in the sky (from an "earth"?)"?

[Gene222]

(10-20-2018 09:35 PM)sasa Wrote:  If both rovers are "blind", i.e. cannot locate it's position and communicate with eventually orbital module when visible, the fastest and dynamic way I can think of is that both go to one of designated magnetic pole.

That way both will not miss each other, both will move cutting searching time on half, saving energy... In worst case scenario, both together will cross less than D to the designated pole, with in less than (D/V)/2. The best case scenario, of course, is when both are close to the designated pole, when both will cross less than D/2 in less than (D/V)/4 time.

This is a variation of sasa's solution, and would be unique to the Earth's moon. Program each rover to travel to the area on the moon, where the Earth is directly above the rover. If a rover has landed on the dark side of the moon, include a program where the rover would travel in a straight line along the plane of the sun and planets, until the Earth becomes in sight. Once the Earth is in sight, maneuver the rover until the Earth is directly above the rover. The worst case travel time would be where the rover travels (EDIT) about 3/4's the circumference of the moon.

[Thomas Okken]

(10-21-2018 12:42 AM)Paul Dale Wrote:  The moon doesn't have a magnetic field so a compass is useless.

A gyrocompass should still work, though. That should enable both rovers to steer toward the north pole and find each other there. As long as you're on a rotating body, anyway...

[ijabbott]

If both rovers leave a permanent trail, they could both head in a great circle. One of the rovers is programmed to stop when it meets a rover trail. The other rover is programmed to continue in the same direction until it meets the other rover. If the rovers are travelling at the same speed, they should meet within two circumnavigations.

[EdS2]

I think the problem is a little harder, and perhaps a little more interesting, if both rovers have to execute the same program. (If you're not careful, they will keep missing each other.)

[pier4r]

(10-21-2018 01:45 AM)sasa Wrote:  The original problem was about two friends left on a big sphere where communication is impossible and question was what is the fastest way to find each other... And that is not a math, but just a brain teaser type of puzzle...

Back to your modification... If there is no way to determine position (including navigation by stars), reference point and direction, this is simply "needle in a haystack" search (without a magnet). What only left is what Tomas wrote, assuming primary rover have unlimited energy, memory to map whole terrain and unlimited time...

Without some more missing details mentioned already, this kind of "brute force" solution only applies...

For me the approach would be.
- Imagine a spherical flat ball, with the two rovers, nothing else. So far Thomas has the only approach on this.
- Ok it is more of a planet. So the idea of a magnetic compass would help. Although some celestial bodies have fleeble magnetic poles. Some have used this idea.
- It is a planet with always clear sky, then navigation with the stars is ok (or there is a ship goign around the planet9. Some have used this idea.

(10-21-2018 06:31 PM)Dave Shaffer Wrote:  Reference as in "a similar celestial body" or as in "something you can see in the sky (from an "earth"?)"?

reference in size, fixed the first post.