Unity navmesh manages to calculate path in Editor but fails when deployed on Android device

Question

I'm working on a game where characters are controlled using a nav mesh agent. For month I did not have any issues with the nav mesh, but I recently have started to grow the scene and having trouble with it. Everything works fine when I test my game in Unity, path are properly calculated and characters move around happily. But when the build is deployed on Android, my characters get stuck. Using the debugger, I can see that pendingPath is always set to true, as if the path is never resolved.

I'm baffled. What would cause this to work on the PC and not an the Android device ? What can I do to investigate further/fix the issue ?

Thanks