Electric vehicles (EVs) have been proposed as a key technology to help cut down the massive greenhouse gas emissions from the transportation sector. Unfortunately, because of the limited capacity of batteries, typical EVs can only travel for about 100 miles on a single charge and require hours to be recharged. The industry has proposed a novel solution centered around the use of "swapping stations," at which depleted batteries can be exchanged for recharged ones in the middle of long trips. The possible success of this solution hinges on the ability of the charging service provider to deploy a cost-effective infrastructure network, given only limited information regarding adoption rates. We develop robust optimization models that aid the planning process for deploying battery-swapping infrastructure. Using these models, we study the potential impacts of battery standardization and technology advancements on the optimal infrastructure deployment strategy. This paper was accepted by Dimitris Bertsimas, optimization.