There are several works that somehow deal with the expensive computation time for edge evaluations in graph-search planning algorithms. Here I explain one of the state-of-art algorithms to deal with this problem, which is lazy weighted A* (LWA).
LWA works as follows. First, LWA assumes that the true edge cost is unknown and later LWA updates the true edge cost during its planning process after edge evaluation is done per edge. To bound the suboptimality of the solution cost, LWA uses non-overestimating cost. Then, once LWA intends to expand the edge, it evaluates the edge to figure out if the edge is collision-free or not.By repeating this process, LWA eventually finds the solution with guaranteed bounded cost.
Reference
B. Cohen, M. Phillips, and M. Likhachev, “Planning Single-arm Manipulations with n-Arm Robots,” Robotics: Science and Systems X, Jul. 2014, doi: 10.15607/rss.2014.x.033.
< bib >
@inproceedings{Cohen_2014, series={RSS2014}, title={Planning Single-arm Manipulations with n-Arm Robots}, url={http://dx.doi.org/10.15607/RSS.2014.X.033}, DOI={10.15607/rss.2014.x.033}, booktitle={Robotics: Science and Systems X}, publisher={Robotics: Science and Systems Foundation}, author={Cohen, Benjamin and Phillips, Mike and Likhachev, Maxim}, year={2014}, month=jul, collection={RSS2014} }