Urban mobility can often be categorized as a complex system—e.g., a nonlinear system composed of many components that interact with each other and have interdependent relationships. Current trends in urban mobility systems point toward shared, more lightweight, and more autonomous vehicles, with planning solutions that are less centralized and can handle increasingly complex transportation networks. In this study, we study planning solutions for shared micro-mobility systems of autonomous vehicles using the MIT Autonomous Bicycle, which has both self-driving and manual driving modes. Vehicle rebalancing in shared micro-mobility systems is a key technical challenge and has a substantial environmental and economic impact. This research proposes a fully decentralized approach for autonomous bicycles to self-organize their own rebalancing based on stigmergy, a bio-inspired mechanism for indirect communication. While the bicycles autonomously navigate their urban environment, they locally update RFID tags at intersections, leaving virtual pheromone trails to collectively guide each other toward high-demand areas. After designing and implementing a realistic agent-based model of a high-demand urban area (Cambridge, USA), this study demonstrates that autonomous bicycles could tackle the vehicle rebalancing problem in a self-organized manner, using strictly decentralized local communication. The proposed method is shown to significantly reduce the average user wait time compared to no rebalancing and random rebalancing.