This paper proposes a two-level optimization approach for a multi-robot navigation problem. Our aim is to achieve tasks with optimal strategies, optimal trajectory planning and to give better and feasible solutions. Optimal alternatives are selected by combining game theory strategic decision with an optimal trajectory planning method. This is solved at the top level by applying Sequential Quadratic Programming (SQP). At the bottom, Pure Nash equilibrium is solved using the Simulated Annealing (SA) algorithm. The trajectory planning for the multi-robot system is performed by decomposition where the b-spline technique is initially used to describe the robots path in an environment with obstacles. The cubic spline technique is then introduced to set up the motion along the desired path. The kinematic and dynamic constraints inherent to the robot behavior are taken into account and collision constraints are handled by penalization. The proposed approach is applied to heterogeneous Unicycle Wheeled Mobile Robots and simulated in endowed obstacles environment. Optimal collision-free trajectories of the robot team are obtained with smooth line paths and good-quality solutions. Simulation results are given to show the effectiveness and robustness of proposed algorithm.