Maybe the Emperor allowed them to travel by boats? Most boats wouldnt go there, of course, because of the way the Empire's attacks on the sea-travel... the Emperor could have easily ordered a boat, but it never says it in the game, of course.