Address Resolution Protocols (ARP) are used in Automated Highway Systems (AHS) to establish communication among vehicles. The purpose of the ARP is to determine the network address of neighboring vehicles. We are proposing an innovative solution that takes advantage of the automated road infrastructure. For providing addresses initially and uses the communication network itself for updating the network communication addresses in a one lane automated highway system. The protocol has been modeled using PROMELA [1], and simulated and verified by SPIN [2]. SPIN is a tool for analyzing the logical consistency of concurrent systems, specifically of data communication protocols. The verification results show that automated vehicles in a single lane remain accurately informed about the communication addresses of their neighbors despite maneuvers (dynamics) on the road.