A navigation functions' based methodology, established in our previous work for centralized multiple robot navigation, is extended to address the problem of decentralized navigation. In contrast to the centralized case, each agent plans its actions without knowing the destinations of the other agents. Asymptotic stability is guaranteed by the existence of a global Lyapunov function for the whole system, which is actually the sum of the separate navigation functions. The collision avoidance and global convergence properties are verified through simulations. (c) 2005 Elsevier Ltd. All rights reserved.