Path planning for multi-vehicle multi-target pursuit (MVMTP) is studied in this paper. With respect to equal number of vehicles and obstacles, a global cost function (GCF) is proposed and an optimal one-vehicle-one-target-pair appointment is specified based on the GCF. The artificial potential (AP)-guided evolutionary algorithm (EA) is used by each appointed pair to search the path that allows the vehicle to catch the target at a specified criterion while avoiding obstacles. Both the targets and obstacles are moving in the environment, and the pair appointment can be updated regularly according to the snapshot of the uncertain environment. The integration of AP into EA is intended to achieve a convergent, fast and efficient trajectory searching mechanism that can be installed in real time