A real-time action search for an autonomous mobile robot using Evolution Strategy (ES) is proposed. By searching optimal actions for facing situations in real time, the robots are relieved from the problems of categorization of the situations and a-priori-definition of rules. The basic idea of the real time action search is to balance computational amount with exactness of solutions. In order to realize this trade-off, a two-stage evaluation technique is introduced under a framework of Anytime Algorithm. The prediction and action watch dog systems are also used. Then, the feasibility is shown through the experimental results.