Abstract: The number of agents and the execution time are two significant performance factors in mobile agent planning. Fewer agents cause lower network traffic and consume less bandwidth. Regardless of the number of agents used, the execution time for a task must be kept minimal, which means that use of the minimal number of agents must not impact on the execution time unfavorably. As the population of the mobile agent application domain grows, the importance of these two factors also increases. After careful review of these two factors, we propose two heuristic algorithms for finding the minimal number of traveling agents for retrieving information from a distributed computing environment, while keeping the latency minimal. Although agent planning, specifically Mobile Agent Planning (MAP), is quite similar to the famous Traveling Salesman Problem (TSP), agent planning has a different objective function from that of TSP. TSP deals with optimal total routing cost, while MAP attempts to minimize the execution time to complete tasks of information retrieval. In this paper, we suggest the cost-effective MAP algorithms, BYKY1 and BYKY2, which can be used in distributed information retrieval systems to find the factors mentioned above. At the end of each algorithm, 2OPT, a well-known TSP algorithm, is called to optimize each agent's local routing path. Experimental results show that BYKY2 produces near optimal performance. These algorithms are more realistic and applicable directly to the problem domains than those of previous works.