With the increasing popularity of location-based services (LBS), the issues caused by users’ location privacy are suffering more and more complicated problems during these years. In this paper, it firstly analyzes the attacks on LBS and the existing protection methods, and then presents a new adaptive routing policy based on mobile multi-agents under LBS environment. For the unique characteristics of multi-agents, the advantages of mobile agents not only ensure the safety of the agent itself, but also protect the privacy of users’ personal information. Then, it presents a multi-agent based adaptive routing policy to improve the speed of selecting the mobile path by using two-level routing tables discussed in this paper. Furthermore, the updating algorithm of improved routing table makes the mobile agents at a lower level of total cost. Finally, we design a simulation experiment to show that the routing policy is feasible, efficient and safe to the LBS platform.