Okay, hmm, so the thing he's doing here is taking advantage of the fact that planes don't spatially map one-to-one against the Void (or z-space), and specifically, different planes have different Void-mappings. So he can cut through Void to the Elemental Plane of Water, 'search' a feasible distance there, and slip back to the Void very 'far away', in a position where his search can more feasibly reach the place that maps to the Andalite homeworld.
The trouble is that really, he probably needs to do that more than once, and that makes it a stupidly complex optimization problem. But he's got a lot of planar maps from near Velgarth, and can get some more near Earth, and he knows the straight-line normal space direction and distance to the Andalite world (it's just not one that anyone can travel across, even in many many lifetimes), and he knows the z-space route too. There's still going to be trial and error involved, but he can make better guesses about what to try.
...The Elemental Plane of Fire and the Abyssal Plane are both very 'dense' and thus can skip across large equivalent-distances in z-space, but also very hostile to magic, so he doesn't want a spell going there for long.
He works steadily on it, twelve hours a day, a lot of it is just staring at computer modeling programs rather than tiring magic. When his brain needs a break he morphs Andalite and practices tail-sparring with the others.