Fastest way to meet, without communication, on a sphere?

Question

I was puzzled by a question my colleague asked me, and now seeking your help.

Suppose you and your friend* end up on a big sphere. There are no visual cues on where on the sphere you both are, and the sphere is way bigger than you two. There are no means of communication. You can determine your relative position and direction by navigating the stars**. You can move anywhere, and your friend too.

Upon inspecting the sphere, you see it is rock-solid, so you cannot create markings. To protect the environment, you are not allowed to leave other stuff, like a blood trace or breadcrumbs.

You have been put on the sphere without being able to communicate a plan.

How would you be able to find each other (come within a certain distance $\epsilon$?) What would be the optimal strategy to move?

*Since you are here, you must be a rational person. For this puzzle we assume your friend is rational too.._{Which makes it odd that you end up on that sphere anyway}

**While you can determine your position relatively, you are on a sphere in a galaxy so far away that you cannot determine absolute 'north', 'south' etc. by the stars.

Answer 1

Move at random.

Any deterministic strategy you choose has a chance that your partner will choose the exactly opposite strategy, so you end up moving along more or less antipodal paths and never meet. So deterministic strategies have to be avoided.

You might make some adjustments to your random strategy. For example, you could prefer to walk longer distances in a straight line as opposed to choosing a completely new direction after every centimeter of movement. Depending on what your partner does, some of that might improve things. But to accurately judge whether it does, you'd need some probabilistic model of what plan your partner is likely to choose, and getting that right would pretty much amount to a pre-agreed plan. So you can't even know the probability distribution of plans for your partner, hence you can't quantitatively compare strategies against one another.

Answer 2

As per "You have been put on the sphere without being able to communicate a plan." I'm going to assume you cannot even assume what plan your partner may come up with and there is no prior collaboration.

Given the potential symmetric nature of the problem, there must be a random element to break that symmetry, should you both accidentally choose mirror strategies. The problem is there's no guarantee that your friend will select an optimal strategy, however, if your friend is smart and/or exhaustive, they will realise two things:

1. If you are both moving, the chances of running into each other can be nil given non-overlapping patterns.
2. If one of you stays still, the other can eventually find you with an exhaustive search.

So the first thing to do is to calculate the size of the sphere (by picking a direction and walking until you arrive back at the start point or some other, more efficient technique). At that point, you can work out an exhaustive search pattern and the duration to perform one (a spiral pattern is close to optimal but difficult for a human to perform). That duration becomes your frequency of decision making.

Once per period, you flip a coin. Heads, you do an exhaustive search. Tails, you stay put. Each of the longer period (e.g. the less efficient search pattern), you have a 50/50 chance of doing the opposite of your partner and thus discovering each other in the course of the exhaustive search.

There's two extreme cases that are covered by this approach. If you partner decides to never move, obviously they will be found on your first exhaustive search. If they decide to permanently move, either randomly, or according to some pattern, there's always the chance of happening upon them accidentally during your search sweeps, which you have to rely on if they're not being exhaustive and their movement does not cover your 'stay put' spot. Otherwise, when you stay put you guarantee they'll eventually find you.

Answer 3

move on spirals like this:

_{(source: forum.cad.de)}

where the distance between spiral arms is $2\epsilon$.

I assume you have a measure of distance on your sphere, or else you couldn't determine the winning condition.

Answer 4

Here there are some points.

1. Here it seems a bit redundant to me to talk about strategies, because it is more of a static game with complete information than a dynamic game.

   First of all, I assume that for you this is a game with complete information. To do so more explicitly, we – roughly – simply have to add to your sentence "There are no visual cues on where on the sphere you both are, and the sphere is way bigger that you two. There is no means of communication. You can determine your position and direction by navigating the stars. You can move anywhere, and your friend too." the words "you both know this, you both know that you both know this, and so on."

   Then, the game is static because the temporal element is not really relevant. You choose an action, your friend another, and that's pretty much it, because you cannot really change what you are doing given what your friend is doing, considering that you have no access to that information. Hence, we can get rid of the term "strategy", that in static games with complete information collapses to the term "action".

2. Now, is any of your actions dominated (i.e. you could take an action that gives you a higher payoff, no matter what your friend does)? Not really. Hence, basically all your actions can be rationalized by some conjecture of your friend. Of course, due to the symmetric nature of the game, the same applies to you.

3. Does the game have a solution? Well, it does depend on the solution criterion you think of, and also on how you conceive it. For example, IMO the game has an obvious Nash Equilibrium (please, note that I am not a rocket astronomer...): you and your friend go north, until you both can roughly find with some rough estimation that you are at the north pole of your sphere, and then you wait that the other shows up. You should end up in some $\varepsilon$ distance to each other. Note that here I am assuming the interpretation of Nash Equilibrium as a self-enforcing agreement. Note also, that this action profile should correspond in an objective correlated equilibrium, where the objective device is roughly the pole star.

PS: Of course, the all point behind points (2) and (3) is in order to define exactly what you think "optimal" means here (something that is always problematic). An additional point is that I am assuming that in order to coordinate, the players need to have some objective reference point (north pole - pole star).

Answer 5

Since you've included stars such that can be navigated from in the problem statement, this means that at least one unique "configuration" of star positions is visible from any given point on the sphere.

From this, I would posit that a better-than-random solution would include finding the most "interesting" such configuration (so first you have to map them all by traveling the sphere methodically) and heading there as a Schelling point. If one's confidence level in a given configuration acting as a Schelling point for the other player is insufficient, a strategy that randomizes a distribution of time spent at each point of interest could be worked out depending on the size of the sphere, ϵ, and confidence level in the "interesting"-ness of each point.

For example, a "default" Schelling point for two players who think like I do would be to seek the unique star configuration with the least component stars. Or, to rephrase it for an Earth-like sky, the recognizable constellation made up of the least amount of stars -- or possibly the brightest star in the sky, if there is one sufficiently brighter than the others.

Answer 6

I think completely random movement is sub optimal.

I think a better strategy is to pick a direction (any will do), stick to it and randomise your speed.

If both parties do this their paths will cross twice each orbit (unless they are on the same orbit in which case they will meet sooner due to randomised speed)

if you go full random changing direction as well as velocity you aren't guaranteed to ever cross the path of the other. (although as t gets large it becomes increasingly likely that your paths will cross at least once.)

Speed randomisation is necessary to avoid never meeting because of resonance.

Convergence will be quickest if both parties adopt the same strategy. If the other party adopts any other rational strategy that doesn't involve being stationary they will meet eventually.

Answer 7

Are you allowed to leave your 'footsteps'? I believe it makes the problem more interesting (otherwise the solution of MvG seems to be correct).

My solution is based on the fact that 2 great circles must intersect on two points (or be the same circle). So I suggest that both persons will start walking in a great circle. Eventually, each one will reach an intersection (or his own starting point, which can be treated in a similar fashion)

In average, it will happen after walking half a circle. we'll call this time $t$

• It might be the same intersection, but on different times
• It might be exact opposite points on the sphere

In the latter case, the situation might be symmetrical (consider the case of two persons landing on the exact opposite points and walking at the same speed on different great circles), so there is no way to decide (without pre-arrangement) who will wait to the other.

This means that the next step should be to randomly decide if you wait for a period of time $\alpha t$ (I'm not sure what is the ideal $\alpha$ is, it's below $2$ if both persons walk at the same speed, and maybe should be randomized as well) (they should be able to know what is $t$ by now) or go to the opposite point. After each period of time you should randomly decide again.

To give a rough estimate of the time it will take, we can assume that the chance to meet at the $n$-th period is $P(n) = \frac{1}{2^n}$, so $E[t_{meeting}] \propto 2 \alpha t$

Answer 8

Dig a hole directly vertically downwards towards the centre of the sphere using a plumb line. Both parties holes will intersect at the centre of the sphere.

Answer 9

• Step 1: Walk in a great circle until the sky is the same, count your footsteps along the way.
• Step 2: I'm assuming you can translate footsteps to units of $\epsilon$. Call the circumference C. Turn $\frac{2\pi \epsilon}{C}$ radians anticlockwise.
• Step 3: Walk in a great circle until the sky is the same.
• Go to step 2

Stop this procedure if at any point you are within $\epsilon$ of your partner.

Since your partner is rational they've assumed the same strategy. Between you and your partner's starting point is a great circle of equidistant locations. Since you and your partner are always walking at the same time, you are always the same distance from your relative starting points.

For each greater circle walked you visit the equidistant circle twice (not necessarily at the same time as your partner). As you explore the equidistant circle in one direction your partner explores it in the opposite direction since she is on the opposite side.

You will meet your partner on the equidistant circle within $\lfloor\frac{C}{\epsilon}\rfloor$ iterations.

Answer 10

I couldn't find my answer by zigzagging the comments/ answers, so here it is

Create breadcrumbs towards your location.

Move a certain distance from your "home" (origin point) and write down an arrow on the ground (or other marker) pointing to your home. Repeat that all around your location so within say 10 ϵ your crumbs can guide someone to the center. By doing this further and further away (then coming back to the center !) you make it easier to find you.

Either your friend will look around exhaustively, or he can do the same thing, and eventually one of you will stumble on an arrow.

If you do find one and your friend isn't at the center, either wait for him, or leave a mark at the center saying you passed here and tried to find him, so you can come back at some point and meet (having a meeting point)

Not really a math answer but a practical one =)

Answer 11

Since the stated problem states that one can navigate by the stars I assume that the sphere is rotating, if not there is meaningful stellar navigation is not possible, IMHO*.

Then, both rational persons, can find 'north' by facing the direction from which the stars appear to rise the fasted, mentally label it 'easterly', face 90 degrees (should i use radians here?) to the left, and label that direction 'northerly.

Then watch the both the northerly and southerly directions looking for stars that don't 'set'. If that group of stars is southerly one is in the southern hemisphere, else in the northern hemisphere.

Memorize the configuration. The two persons can reduce the distance between them by both walking north.

A . If in the northern hemisphere walk toward the target stars each night. One can estimate the latitude and progress by subtracting the estimated elevation from 90 degrees. When the stars are directly overhead stop and start a search.

For instance at regular intervals try a random walk for a distance much greater than ϵ and at every stop do a random walk for a distance a bit larger than ϵ perhaps resting for a few days. (Some animals have a search pattern if this sort - without the rest - but I have forgotten the name of the pattern.) Don't stray too far from the north pole.

B If in the southern hemisphere walk away from it at night until the target stars are setting. At this point notice the stars to the north that only rise a little bit before setting; this will be north and proceed as above (A).

• If the sphere is not rotating there is no way of each person finding 'north'. Walking in a great circle, as has been suggested, by walking toward a specific star breaks down when the star disappears at the horizon or when the star approaches zenith unless one can find a set of stars that are in a line.

I'm assuming that a line cannot be scratched on the sphere that the other might come across and follow.

Answer 12

You can't have an optimal solution for this problem.

Let's assume one possible scenario of this system:

"That whatever you do the other person would do the opposite."

So this becomes a case similar to Quantum Entanglement. You can never find out the present state of both particles. In this case the position.

Second problem is that at any givem time your destination is assumed to be every point on the sphare -distance in sight. So if you destination isn't a set point you can't plot an optimal course. (given the information and no loopholes)

Answer 13

Assuming this sphere is like an exercise ball... and that there is no wind, no animals, and somehow the two of you need no food for the time being.

Take off one shoe. Point it in a direction of your choosing, and walk in that direction - straight. If (you should) return to that point, modify your angle (do not change the direction of the shoe) so that you circumnavigate in a different direction. You'll eventually traverse "most" of the surface area, and your walking speed will be different than your friend. You will eventually come within some distance of each other, such that you can see each other. That's the solution.

2nd solution. If you really could discern straight lines/curves, then your goal would be to find the path such that you are walking the full circumference. You can do this by counting your steps. If you know that your circular path is now the full circumference (and your friend does the same), your different walking speeds would lead to to be within some range of each other eventually that you see each other.

Answer 14

solution of Steve Cox. Once you cover all sphere and back to lending point, choose random turn at step 2. You friend does exactly the same and even if you move from opposite poles doing exactly the same with same walking speed - you will meet.

Answer 15

Suppose there is any way to identify special points on the sphere [see below], the optimal strategy would be to identify the maximally "prominent" special point or points, and spend a randomized amount of time at each one. This reduces the dimensionality of the problem from meeting on a sphere to meeting on a finite number of points. As @gerrit pointed out in a comment under the question, this is a difficult problem even with three locations; but certainly it will admit more efficient solutions than meeting on a sphere with no features.

But what special points? Even though the sphere itself has no features (and we cannot leave any marks), you don't need a familiar sky to identify the poles. So if we're allowed to use the planet's rotation as information, I'd identify the two poles and then spend a random amount of time in each pole, then move to the other. If my counterpart adopts a similar strategy (and by symmetry we can expect him/her to do so), the odds that we remain at opposite poles approach zero over time. I can name the poles "North" and "South" according to the direction of rotation (as pointed out by @Kundor), but I wouldn't be 100% confident that if I choose North, the other person will too. Still, narrowing it down to two points is not bad at all.

Even if the planet does not rotate, I can still look for the brightest star and go hang out directly below it for a while (moving along as the planet rotates). In fact, even if the planet rotates there are moving special points, e.g. "the point that is currently directly under the brightest star [or under the sun]".

All that said, I'm pretty sure the point of the question is to optimize a scan of the sphere's entire surface with maximum probability of intersection, so any "special points" are considered off-topic. Perhaps the planet is covered by clouds, but the participants have some sort of inertial device that measures displacement but cannot determine the axis of rotation. Or they are actually not on a planet's surface but in the stomach of a spherical cow, and it's dark...

Answer 16

Perform the following steps until you find your friend:

1. Figure out a path (based on the stars) that checks the entire sphere and walk it, returning to your starting point. The time it takes you to walk this is t.
2. Flip a coin (or a your shoe, or whatever...).
   
   • If Heads: Goto step 1
   • If Tails: Wait t and then repeat step 2

Notes:

1. If both you and your friend accept this strategy
   • You might luckily meet on your first trip around the sphere
   • If you don't meet the first trip and t is approximately the same for both of you, you'll likely meet the first time you and your partner get a different value for your coin flip (one of you will be resting when the other is moving)
   • If you don't meet the first trip and t is quite different for both of you, each time you unknowingly pass your friend's "home base" after the first trip, the odds of finding them resting are 1 in 2. You also may cross paths while both traveling.
2. If your friend picked a different strategy
   • If they rest until you find them: You'll find them on the first trip
   • If not: They will have a 1 in 2 chance of finding you each time they pass your home base after your first trip. Otherwise, you will have a chance at finding them during each trip you take around the sphere based on whatever strategy they chose and their starting location

Answer 17

MvG got it half right.

He is correct that your strategy must be random to avoid mirror image problems. He even correctly concludes that a random walk is not a good strategy--but then fails to make the final step:

Figure out a coordinate system for the sphere.

Walk to a random point on the sphere, repeat until you find your friend.

If you have the means to do so getting higher up is of value so long as you don't get so high that you fail to spot your friend due to distance rather than him being below the horizon. From the problem description I think it unlikely that you have access to spacecraft but for spheres with a diameter of no more than a dozen or so miles just your legs will be of benefit.

There have been requests for an estimate of the duration. Since this is random any estimate by it's nature is also random. As you move you observe a new area equal to a stripe your sight distance wide (it's actually a crescent but the area is the same--look at the area of a racetrack to see this.) Thus the odds of finding your friend is your sight distance * your movement speed / the area of the sphere. All distances must be in the same unit, the odds are per the time unit used in the movement speed.

Note how this is linear on sight distance, if you can increase your sight distance with jumping more than you lose in speed by jumping instead of just walking do so. Since our natural movement in low-g appears to be kangarooing anyway one should go with this.

Answer 18

In examples of this in 2D that I've heard, if I recall the answer is:

• Mark the spot you landed and remember it. Leaving the parachute you used behind will suffice.

• Travel back and forth in increasingly large distances away from your landing site. (IE: 1 yard west of site, 2 yards east of site, 3 yards west, etc.)

• If you encounter a second parachute, stop and wait.

• Assuming you don't run out of fuel, you will eventually either encounter the other robot, or its landing site.

In 3D, that becomes a lot trickier. Rather than back and forth, as someone else mentioned, you could use spirals. You would then eventually encounter the second landing site. But then, what do you do when you find it? If the rule is "wait at the second landing site", the other robot may never return.

Either you need to return to your own landing site at regular intervals (like once every 360 degrees) and check to see if the other robot is waiting there, or once you find the second landing site, start traveling between it and your own landing site. In each of these, you should eventually encounter the other robot.

Thinking a little more about it, returning to your own landing site as you search may not work, since you might both find the other site at the same time and stop, so you would have to start going back and forth from one site to the other once you found the second site.

I have no idea if this is optimal, though.