The increasing integration of Electric vehicles (EVs) and renewable generators (RGs) is an inevitable trend of power grid concerning the global control of greenhouse gas release. This will challenge constrained distribution networks due to the intrinsic intermittency of renewable power and additional charging load demand of EVs. However, appropriate dispatch of EVs via vehicle-to-grid (V2G) operation in coordination with RGs can solve the stability issues, provide operational support for the power grid, reduce the reliance on fossil fuels and benefit both the environment and EV users. This paper develops a novel algorithm to solve the optimal decentralized coordinated dispatch problem of RGs and EVs based on multi-agent and the A∗ search procedure. This optimal dispatch problem is formulated as a distributed multi-objective constraint optimisation problem using the Analytic Hierarchy Process taking into account both power grid and EV users’ concerns and priorities. The inherent uncertainty of EV driving activities and RG output power are considered in this work, of which the stochastic modelling is established using copulas. The proposed algorithm is tested on a radial distribution network, a modified UK generic distribution system. The simulation results demonstrate the feasibility and stability of the proposed A∗-based optimal coordinated dispatch strategy.