Motor proteins display widely different stepping patterns as they move on microtubule tracks, from the deterministic linear or helical motion performed by the protein kinesin to the uncoordinated random steps made by dynein. How these different strategies produce an efficient navigation system needed to ensure correct cellular functioning is still unclear. Here, we show by numerical simulations that deterministic and random motor steps yield different outcomes when random obstacles decorate the microtubule tracks: kinesin moves faster on clean tracks but its motion is strongly hindered on decorated tracks, while dynein is slower on clean tracks but more efficient in avoiding obstacles. Further simulations indicate that dynein's advantage on decorated tracks is due to its ability to step backwards. Our results explain how different navigation strategies are employed by the cell to optimize motor driven cargo transport.