Recently, Wireless Sensor and Actor Networks have been receiving a growing attention from the research community because of their suitability for critical applications. Maintaining inter-actor connectivity becomes extremely crucial in such situations where actors have to quickly plan optimal coordinated response to detected events. Failure of critical actor partitions the inter-actor network into disjoint segments, and thus hinders the network operation. Autonomous detection and rapid recovery procedures are highly desirable in such case. This paper presents PCR, a novel distributed partitioning detection and connectivity restoration algorithm. PCR proactively identifies critical actors based on local topological information and designate appropriate backup nodes (preferably non-critical) to handle their failure. A backup actor detects the failure and initiates a recovery process that may involve coordinated multi-actor relocation. The purpose is to avoid procrastination, localize the scope of recovery process and minimize the movement overhead. Simulation results validate the performance of PCR that outperforms contemporary schemes found in literature. © 2010 IEEE.