There are many variants of A* that can handle changing environments/imperfect information, multiple goals, limited time, etc. A number of them are listed at:

http://idm-lab.org/project-a.html