Autonomy is a puzzling phenomenon in nature and a major challenge in the world of artifacts. A key feature of autonomy in both natural and artificial systems is seen in the ability for independent exploration. In animals and humans, the ability to modify its own pattern of activity is not only an indispensable trait for adaptation and survival in new situations, it also provides a learning system with novel information for improving its cognitive capabilities, and it is essential for development. Efficient exploration in high-dimensional spaces is a major challenge in building learning systems. We propose to implement the exploration as a deterministic law derived from maximizing an information quantity. More specifically we use the predictive information of the sensor process (of a robot) to obtain an update rule (exploration dynamics) of the controller parameters. To be adequate in robotics application the non-stationary nature of the underlying time-series have to be taken into account, which we do by proposing the time-local predictive information (TiPI). Importantly the exploration dynamics is derived analytically and by this we link information theory and dynamical systems. Without a random component the change in the parameters is deterministically given as a function of the states in a certain time window. For an embodied system this means in particular that constraints, responses and current knowledge of the dynamical interaction with the environment can directly be used to advance further exploration. Randomness is replaced with spontaneity which we demonstrate to restrict the search space automatically to the physically relevant dimensions. Its effectiveness will be presented with various experiments on high-dimensional robotic system and we argue that this is a promising way to avoid the curse of dimensionality. This talk describes joint work with Ralf Der and Nihat Ay.