Sébastien Dalibard

Antonio El Khoury

Florent Lamiraux

Alireza Nakhaei

Michel Taïx

Jean-Paul Laumond

Dynamic Walking and Whole-Body Motion Planning for Humanoid Robots: an Integrated Approach

This paper presents a general method for planning collision-free wholebody walking motions for humanoid robots. First, we present a randomized algorithm for constrained motion planning, that is used to generate collision-free statically balanced paths solving manipulation tasks. Then, we show that dynamic walking makes humanoid robots small-space controllable. Such a property allows to easily transform collision-free statically balanced paths into collision-free dynamically balanced trajectories. It leads to a sound algorithm which has been applied and evaluated on several problems where whole-body planning and walk are needed, and the results have been validated on a real HRP-2 robot.

Introduction

During the last twenty years, impressive progress has been achieved in humanoid robot hardware and control. This leads to a rising need for software and algorithms improving the usability and autonomy of those robots. One important area of research focuses on the development of robust and general motion generation techniques for safe and autonomous operation in human environments, such as offices or homes.

Motion planning for humanoid robots is challenging for several reasons. First, the computational complexity of classic motion planning algorithms is exponential in the number of Degrees of Freedom (DoFs) of the considered system, which is high for humanoid kinematic trees. Second, a humanoid robot is an under-actuated system: the DoFs that control the position and orientation of the whole robot in space are not directly controlled, they derive from the articular DoFs of the robot legs. Those latter should be controlled with care to guarantee dynamically balanced motions, for manipulation or navigation.

When planning collision free motions for humanoid robots, different representations of the robot and its environment can be used. The choice of the level of details of the representation indicates the difficulty of the considered problem. The simplest option consists in considering the robot as a navigating 2D shape [START_REF] Pettré | A 2-stages locomotion planner for digital actors[END_REF], and computing obstacle avoidance in a planar model of the world. Another possibility is to compute only collision-free footsteps [START_REF] Kuffner | Footstep planning among obstacles for biped robots[END_REF]. In complex and difficult environments, such as the one presented in Fig. 1, it can be necessary to consider exact 3D models of a humanoid robot and its environment.

Figure 1: The robot HRP-2 passing between two chairs. In this kind of environment whole-body collision avoidance is needed during locomotion.

There are two main ways of using motion planners to generate dynamically balanced robotic motions. The more general one is to plan in a robot dynamic space, see for example [START_REF] Shkolnik | Bounding on rough terrain with the littledog robot[END_REF]. By taking into account both robot configuration and velocity, motions that satisfy dynamic balance constraints can be generated at a planning phase. When planning motion for humanoid robots, this is a particularly costly approach, as the size of the space to explore is augmented with the robot velocity and footprint positions. The other way is to first plan a geometric path that can be approximated by a dynamic trajectory in a second step [START_REF] Yoshida | Humanoid motion planning for dynamic tasks[END_REF]. The approach we present in this paper falls into the second category. Some feasible dynamic motions are inherently impossible to compute with this kind of approach. For example, jumping motions cannot be generated by a purely geometric planner.

In this paper, we present a planning algorithm that considers exact models of a humanoid robot and its environment. It is used to solve navigation and manipulation problems. Our planner is a two-step algorithm: a first collisionfree path is computed in the space of quasi-statically balanced configurations, then this first path is approximated by a sequence of dynamic walking trajectories. The proof of correctness of the algorithm is based on the concept of small-space controllability. This property allows, under some assumptions, to approximate any non necessarily admissible path, by a sequence of admissible trajectories. In our context we prove that dynamic walking makes humanoid robots small-space controllable. Our planner is designed for perfectly modeled indoor environments, where the floor is horizontal and flat. Also, because we do not explicitly compute footprint positions at the planning stage, our planner is unable to plan motions in which the robot steps over obstacles. These limitations are discussed in the paper.

Outline

Section 2 reviews the related work and states our contribution. Section 3 presents a constrained motion planning algorithm, and its use on a humanoid robot manipulation problem. Section 4 generalizes the previous algorithm to problems that require locomotion. The generalization is well-grounded, and based on a controllability property of legged robots demonstrated in the paper. Section 5 presents some experimental results, and Section 6 discusses the limitations and potential future work of our method.

Related Work and Contribution

This work is based on several fields of humanoid robotics research: prioritized inverse kinematics, randomized whole-body motion planning and walk pattern generators based on the Zero-Moment Point (ZMP). This section summarizes the literature related to each of these fields.

Prioritized Inverse Kinematics

The problem of inverse kinematics for a humanoid robot, or any articulated structure, is to compute a joint position to achieve an end-effector pose. As the robots we deal with are redundant, it is natural to take advantage of this redundancy by specifying multiple tasks, potentially with different priorities. This problem has been widely studied in robotics planning and control literature, and many Jacobian-based solutions have been proposed, among which [START_REF] Nakamura | Inverse kinematic solutions with singularity robustness for robot manipulator control[END_REF], [START_REF] Siciliano | A general framework for managing multiple tasks in highly redundant robotic systems[END_REF], [START_REF] Baerlocher | Task-priority formulations for the kinematic control of highly redundant articulated structures[END_REF] and [START_REF] Khatib | Whole body dynamic behavior and control of human-like robots[END_REF]. Obstacle avoidance can be taken into account with similar methods. To do so, one has to include the obstacles as constraints to satisfy, see for example [START_REF] Kanehiro | A Local Collision Avoidance Method for Non-strictly Convex Polyhedra[END_REF]. These methods are prone to fall into local minima, thus global motion planning is needed to overcome this limitation. Note that when local methods find solutions, these are usually smoother and may look more natural. The choice of using global motion planners is justified by the need for complete algorithms. [START_REF] Toussaint | Optimization of sequential attractor-based movement for compact behaviour generation[END_REF] propose a motion generation method where tasks follow trajectories defined by cubic B-splines. The whole-body motion is optimized with respect to the control point positions. This method can take into account collisions with simple obstacles.

Whole-Body Motion Planning

When planning a whole-body motion for a humanoid robot, one difficult challenge is to cope with the curse of dimensionality. The complexity of motion planning is exponential in the dimension of the configuration space (C) to explore. When dealing with high-dimensional configuration spaces, it is typically impossible to explicitly represent them, leading to the use of randomized sampling techniques to solve global planning problems. In the past fifteen years, Probabilistic Roadmaps [START_REF] Kavraki | Probabilistic roadmaps for path planning in high-dimensional configuration spaces[END_REF] and Rapidly exploring Random Trees (RRT) [START_REF] Kuffner | RRT-connect: An efficient approach to singlequery path planning[END_REF] have been developed and used to solve many high-dimensional planning problems, see [START_REF] Lavalle | Planning Algorithms[END_REF] and [START_REF] Choset | Principles of Robot Motion: theory, algorithms, and implementation[END_REF] for comprehensive overviews. When using sampling techniques on a humanoid robot, another difficulty is to take into account balance constraints, i.e. to generate random configurations on zero volume submanifolds of C. This problem has been investigated with success during the last few years, [START_REF] Berenson | Task space regions: A framework for pose-constrained manipulation planning[END_REF]) presents an exhaustive survey of Jacobian-based methods. Other recent contributions [START_REF] Porta | Randomized path planning on manifolds based on higher-dimensional continuation[END_REF] present sophisticated constrained motion planning techniques based on higher-dimensional continuation. Section 3 presents a simple adaptation of the RRT algorithm to constrained motion planning, that was first introduced in [START_REF] Dalibard | Whole-body task planning for a humanoid robot: a way to integrate collision avoidance[END_REF]).

Walk Pattern Generation

Another field of humanoid robotics research is the generation of dynamically balanced walk patterns. Since the introduction of the ZMP [START_REF] Vukobratovic | Contribution to the synthesis of biped gait[END_REF], several methods have been proposed to generate walking motions efficiently. One way to deal with the complexity of a humanoid robot kinematic tree is to use the so-called "cart-table" simplified model [START_REF] Kajita | Biped walking pattern generation by using preview control of zero-moment point[END_REF]. Based on this model, planning a trajectory for the ZMP is reduced to planning a trajectory for the Center of Mass (CoM) of the robot. Given a trajectory of the CoM and footprint positions, inverse kinematics solvers can animate the whole set of DoFs of the robot to generate a dynamically balanced walk trajectory.

Collision-Free Walk Planning

Collision-free locomotion trajectories are usually obtained by simplifying the model of either the robot or the environment. By reducing a humanoid robot to a bounding volume that wraps the swaying motion, one can use a simple planar motion planner on this bounding volume and generate a valid locomotion trajectory. This strategy is used in [START_REF] Pettré | A 2-stages locomotion planner for digital actors[END_REF]) in a computer animation context. Variants of this method include dynamic path reshaping [START_REF] Yoshida | Humanoid motion planning for dynamic tasks[END_REF]: if collisions appear when animating the locomotion trajectory, it is locally reshaped and re-animated. This two-stage strategy does not guarantee that the locomotion trajectory can be followed or that the local reshaping will converge.

One possible simplification of the environment consists in considering obstacles at a footstep level only. [START_REF] Kuffner | Footstep planning among obstacles for biped robots[END_REF][START_REF] Chestnutt | Footstep planning for the Honda ASIMO humanoid[END_REF][START_REF] Kuffner | Motion planning for humanoid robots[END_REF]) use an A * algorithm to find collision-free footsteps. In [START_REF] Perrin | Fast humanoid robot collision-free footstep planning using swept volume approximations[END_REF], the authors compute dynamic walking motions avoiding collisions at the leg level by using an RRT algorithm.

Some planning methods for free-climbing robots [START_REF] Bretl | Motion planning of multi-limbed robots subject to equilibrium constraints: The free-climbing robot problem[END_REF]) can be seen as a general way to consider quasi-static multi-step planning. They are not however directly applicable to humanoid dynamically balanced locomotion. Other recent contributions to the field of locomotion planning include algorithms considering the dynamics at the planning phase [START_REF] Shkolnik | Bounding on rough terrain with the littledog robot[END_REF]. This leads to a growth of algorithmic complexity, particularly costly for high-dimensional systems such as humanoid robots. To the authors' knowledge such techniques have not been used on humanoid robotic platforms so far.

We show in this work that, under some assumptions, it is sufficient to plan a first path in the quasi-static configuration space of a humanoid robot, and then use the small-space controllability property to approximate this path by an admissible trajectory, i.e. a dynamically balanced walking motion. This result was first presented in [START_REF] Dalibard | Small-space controllability of a walking humanoid robot[END_REF].

Contribution

The main contribution of this work is a whole-body motion planner for humanoid robots that computes collision-free walking trajectories, based on exact models of both robot and environment. It is used to solve manipulation tasks that may require walking. The first stage of our algorithm uses a sampling-based constrained motion planner and computes a collision-free statically balanced path for a robot which can be fixed or sliding on the ground.

Another contribution of this paper is the formal proof that dynamic walking makes humanoid robots small-space controllable, with the direct implication that this first path can always be approximated by a dynamically balanced, collision-free walking trajectory. We have implemented this well-grounded method, and the results have been validated on the HRP-2 robot.

Randomized Motion Planning on Constraint Manifolds

This section presents an algorithm for constrained motion planning on a submanifold M of the configuration space C. In the particular case of a humanoid robot which is an under-actuated system, C = Q × SE(3), where Q represents the kinematic tree actuators and SE(3) represents the position in space of the root of the tree. If the robot has n actuated DoFs, then dim(Q) = n and dim(C) = n + 6. A configuration q of C is said to be valid iff, besides being collision-free, it lies on the manifold M; we call M the planning manifold.

The problem solved here differs from classic approaches in two ways:

1. the set of valid configurations is defined implicitly, as the set of collisionfree configurations satisfying a given set of inverse kinematics balance constraints;

2. the goal manifold M g is also defined implicitly, by additional inverse kinematics constraints.

During global planning, we will consider several types of constraints for various reasons:

-Static balance: the CoM of the robot stays above the support polygon center, the two feet are horizontal on the ground.

-End-effector position and orientation: the goals of some problems presented in the experimental section of this paper are defined as a specific robot hand pose, or a gaze direction.

-Configuration task: our adaptation of randomized motion planning algorithms uses tasks defined as the distance towards a given configuration in C. This will be detailed in the following section.

Our algorithm generalizes randomized tree expansion strategies, introduced in both [START_REF] Hsu | Path planning in expansive configuration spaces[END_REF] and [START_REF] Kuffner | RRT-connect: An efficient approach to singlequery path planning[END_REF] to constrained motion planning problems. Next subsection will recall the structure of the RRT algorithm, a popular randomized motion planning algorithm. Our method could be applied to any randomized sampling planning method, such as RRT * (Karaman & Frazzoli 2011), which is slower than RRT but generates optimal paths.

Rapidly exploring Random Trees (RRT)

The classic RRT algorithm, as presented in [START_REF] Kuffner | RRT-connect: An efficient approach to singlequery path planning[END_REF], grows a random tree inside the robot collision-free configuration space C f ree . Each iteration of the algorithm attempts to extend the tree by adding new vertices in the direction of a randomly selected configuration q rand . Algorithm 1 shows the Algorithm 1 RRT(q 0 ) T .Init(q 0 ) for i = 1 to K do q rand ← Rand(C) q near ← Nearest(q rand , T ) Extend(T , q near , q rand ) end for pseudo-code of the RRT algorithm. It takes as input an initial configuration q 0 and grows a tree T rooted in q 0 .

One way to make the RRT algorithm more efficient is to grow trees from both the initial and goal configurations. This was first proposed in [START_REF] Kuffner | RRT-connect: An efficient approach to singlequery path planning[END_REF]. Our formulation of manipulation planning does not include an explicit goal configuration, so it is not possible to directly grow a tree from the goal. To make use of the idea of growing multiple trees, we first randomly sample the goal manifold and generate several goal configurations. Then, we grow random trees from the initial configuration and the random goal configurations. The idea of generating several goals for manipulation planning was proposed in [START_REF] Diankov | Bispace planning: Concurrent multi-space exploration[END_REF].

Section 3.2 describes a constraint solver, Section 3.3 the goal manifold sampling, and Section 3.4 the adaptation or RRT random extensions to constrained motion planning.

Constraint Solver

We show here how a multiple constraint solver works: its purpose is to find the root q of a non-linear C 1 function f (q) with a tolerance of . If we want to find a configuration on a manifold M, f (q) can be defined as a vector valued function that contains the concatenation of all constraints defining M. Note that as the intersection of two or more manifolds is also a manifold, this constraint solver allows us also to generate configurations that lie at the intersection of several manifolds.

Algorithm 2 implements a Newton-Raphson method [START_REF] Bonnans | Numerical optimization: theoretical and practical aspects[END_REF]: starting from an initial value of q, q is updated iteratively by -α ∂f ∂q (q) + f (q), where α denotes a gain and ∂f ∂q (q)

+ denotes the Moore-Penrose pseudo-inverse of the Jacobian of f (q). The use of an adaptive gain α, which increases iteratively from an initial value α to a maximum value α max , allows the overshoot avoidance and convergence acceleration. The update rule relies on a real factor w ∈ [0, 1]; the greater w is, the faster α will reach α max .

Obviously, the solver convergence depends on the initial value of q, and a bad initialization can lead to either slow convergence or failure. A cutoff number of iterations it max is hence introduced to bypass these cases.

We observed that values of = 10 -6 , α = 0.1, α max = 0.95 and w = 0.8 lead to good behavior, i.e. fast convergence and low failure rate. These values are kept constant for all scenarios in this work.

Algorithm 2 SolveConstraints(q, f, ): find q such that f (q) = 0 i = 0 while f (q) > and i ≤ it max do // (.) + denotes the Moore-Penrose pseudo-inverse

q ← q -α ∂f ∂q (q) + f (q) i ← i + 1 // Make α tend toward α max α → α max -w(α max -α) end while if f (q) ≤ then return q else return failure end if

Goal Manifold Sampling

The way we generate a goal configuration is the following:

1. Shoot a random configuration q rand in C with uniform distribution.

2. Call SolveConstraints (Algorithm 2) on q rand , with f (q) defined by the intersection of the planning and goal manifolds M ∩ M g .

3. If success, check for collisions.

Fig. 2 shows resulting random configurations which satisfy both balance (M) and reaching (M g ) constraints for the HRP-2 robot.

Random Extensions on a Constrained Manifold

Fig. 3 shows an extension of the classic RRT algorithm, from a configuration already in the tree q near towards a random configuration q rand . q near T q new q rand Obstacle Figure 3: One step of extension of the RRT algorithm. The algorithm tries to add the longest possible edge from q near towards q rand , while avoiding collisions.

The equivalent random extension on a constrained manifold M, defined by the constraint function f , starts from a valid configuration q near ∈ M, and extends the tree towards a random configuration q rand , while keeping the constraints satisfied. Extension attempts orthogonal to M are useless, as newly added edges have to be included in M. To extend in directions that follow the directions of M, we rely on Jacobian-based inverse kinematics. Algorithm 3 presents the adaptation of the classic extend function, and Fig. 4 illustrates this extension. The idea is to first project q rand on the tangent space to M at q near . Let us call the projected configuration q rand . Let q rand be the result of a call to SolveConstraints(q rand , f, ). It is the projection of q rand on M. Instead of extending the tree from q near towards q rand , the algorithm tries to extend from q near towards q rand while remaining on M1 . While extending the tree, the configurations along the new edge are automatically projected onto M. These projections are not very costly if the edge is close to the constrained manifold. (Berenson, Srinivasa & Kuffner 2011a) presents a formal proof that projectionbased constrained random motion planning on a fixed dimension manifold is probabilistically complete. This proof applies to our algorithm.

Example

We present in Fig. 5 an illustration of the use of randomized motion planning on complex manipulation problems. The humanoid robot HRP-2 faces shelves. It has to: (i) grasp a ball lying on a shelf, (ii) put it on a higher shelf, (iii) come back to a natural rest configuration. We can hence define three separate constrained motion planning problems where the planning manifold M is the static balance manifold defined in 3; the goal manifold of problem (i) is defined Obstacle Constrained manifold M q near q rand TqM q rand q rand q new Figure 4: One step of constrained extension illustrating Algorithm 3: q rand is first projected on T q M the tangent space of M. q rand is then projected onto M. A classic RRT extension tries to go as far as possible from q near towards q rand while remaining on M. q new is then returned.

Algorithm 3 ConstrainedExtend(T , q near , q rand , f, ) d ← Distance(q near , q rand ) q ← q near while d > do q rand ← OrthogonalProject(q rand , T q M) q rand ← SolveConstraints(q rand , f, ) d ← Distance(q, q rand ) q ← q rand end while q new ← RRT::Extend(T , q near , q rand ) by a hand pose constraint (the hand must be horizontal and its position has to coincide with the ball initial position), and a gaze constraint (the robot has to look at the ball in its initial position). Similarly, the goal manifold of problem (ii) is defined by hand and gaze constraints that correspond to the position of the ball on the higher shelf. Finally, we define the rest configuration as the single goal configuration for problem (iii).

Note that for phases (i) and (iii) the ball is also considered as an obstacle. This is necessary to prevent the robot grasping hand from colliding with the ball during the approach (respectively retraction) phase.

For the two reaching motions in (i) and (ii), we first generate 8 random goal configurations (Section 3.3), then we solve the three constrained motion planning problems separately. As randomized motion planning algorithms produce, a classic shortcut method is used to optimize and shorten the paths. Extension 1 presents a video of the concatenated motion.

We piled in Table 1. We have also measured the performance of SolveConstraints (Algorithm 2) when used to project configurations on M; the average number of iterations is 6.5 per call, and the success rate, i.e. the ratio of the number of successfully projected configurations over the total number of calls, is above 95 percent. This success rate, high as it is, could be further improved by sampling a better initial configuration of C, for example by introducing a heuristic bias towards statically balanced configurations. Nevertheless we choose to sample C uniformly-randomly for the sake of genericity. This section presents a constructive proof that any such statically balanced, collision-free path for a legged robot sliding on the ground can be approximated by a dynamically balanced, collision-free walk trajectory. The proof is based on ideas from control theory, in particular small-space controllability. It also uses the fact that balance criteria for dynamic walking are different from the ones for static balance.

Section 4.1 recalls the definition of small-space controllability and its use in motion planning. Section 4.2 proves that a dynamically walking legged robot is small-space controllable, while a quasi-statically walking legged robot is not. Section 4.3 shows how this property is used to approximate collision-free statically balanced paths by dynamic walking trajectories.

Small-Space Controllability

A robotic system is controllable if for any two configurations q 1 and q 2 , there exists a trajectory going from q 1 to q 2 . It is small-space controllable if for all configurations q, for all > 0, there exists η > 0 such that all the configurations contained in the ball of center q and radius η are reachable by trajectories included in the ball of center q and radius . Fig. 7 shows an illustration of this property.

The main consequence of this property in motion planning is the following theorem, that shows how planning for dynamic systems is reduced to geometric q q B (q) η B η (q)

Figure 7: The small-space controllability local property: any configuration q at a distance less than η is reachable from q by an admissible trajectory included in a ball of size .

planning thanks to the small-space controllability property:

Theorem 1. Any collision-free path of a small-space controllable system can be approximated by a sequence of both collision-free and admissible trajectories. Thus, small-space controllability reduces trajectory planning problems to geometric path planning problems.

Fig. 8 shows an example of collision-free path approximation by admissible collision-free sub-trajectories. The convergence of this algorithm is guaranteed by the small-space controllability property. q 2 q 1 C Obstacles Figure 8: Small-space controllability in motion planning. A collision-free path from q 1 to q 2 is approximated by collision-free and admissible trajectories by using the local property. This result has been long known and used in motion planning, in particular for non-holonomic systems. A detailed proof can be found in [START_REF] Laumond | A motion planner for nonholonomic mobile robots[END_REF]. We will present a sketch of the proof to give an intuition about the corresponding algorithm.

Proof of Theorem 1. Let C be the configuration space of a small-space controllable robot, and C f ree ⊂ C the set of collision-free configurations. We consider incontact configurations as colliding, so C f ree is an open set. Let τ : [0, 1] → C f ree be a collision-free path. Thus for all x ∈ [0, 1], τ (x) ∈ C f ree , there exists x such that the open ball B(τ (x), x ) of center τ (x) and radius x is included in C f ree . The small-space controllability property states that for all x, there exists η x > 0 such that every configuration q ∈ B(τ (x), η x ) is reachable from τ (x) by a trajectory included in B(τ (x), x ).

The set of open balls (B(τ (x), η x )) x∈[0,1] forms an open cover of τ ([0, 1]) which is compact. The Heine-Borel theorem [START_REF] Fitzpatrick | Advanced calculus[END_REF] states that there exists a finite subcover (B(τ (x i ), η xi )) i∈{1,...,n} of τ ([0, 1]). To this finite subcover corresponds a finite number of feasible trajectories, going from τ (0) to τ (1), included in the union of (B(τ (x i ), xi )) i∈{1,...,n} , and thus in C f ree . This concludes the proof.

Small-Time versus Small-Space Controllability

In the control theory literature, the property used is usually small-time controllability, which states that for all configurations q, for all times T > 0, the set of configurations accessible from q in time less than T forms a neighborhood of q. When accelerations and velocities are bounded, small-time controllability implies small-space controllability. This is why a lot of motion planning previous work only refers to the sufficient small-time controllability property. However, the reciprocate is not necessarily true: a system can be small-space controllable and not small-time, if the trajectories generated by its controller are arbitrarily long. The important property, regarding motion planning application, is small-space controllability, as Theorem 1 shows. In the following, we show that legged robots are small-space controllable, but not that they are small-time controllable. In fact, the control method that we present does not follow the small-time controllability property. For the sake of clarity, we have chosen to make the distinction between these two controllability properties.

Dynamic Walking Makes Humanoid Robots Small-Space Controllable

This section discusses a walking robot small-space controllability. To clarify the presentation, we consider a simplified model of a legged robot consisting of two feet of zero mass and a point mass free to move in three dimensions. We do not consider the kinematic chains between the feet and the mass. The robot is walking on a flat terrain, and the feet are assumed to have a positive surface. For our presentation, it is not necessary to consider the foot height, so the configuration space of the robot is:

C = SE(2) × SE(2) × R 3
It is of dimension 9. The balanced walking conditions for a quasi-static walking robot are that the point mass, or CoM, should always be over the support polygon (the convex hull of the two feet), and one foot can move iff the CoM is over the other foot. Similarly, the walking conditions for a dynamic walking robot are that the ZMP should always be in the robot support polygon, and one foot can move iff the ZMP is over the other foot. For a precise description of dynamically balanced walking conditions, the reader can refer to [START_REF] Wieber | On the stability of walking systems[END_REF]. Under these assumptions, the following result holds: Theorem 2. A quasi-statically walking robot is not small-space controllable. A dynamically walking robot is.

Proof of Theorem 2. The first claim is straightforward. Let the robot be in a configuration q where the two feet are separated by a positive distance. Let L > 0 be the positive horizontal distance between the CoM and the left foot (if the CoM is over the left foot, we can consider similarly the right foot). For all < L, any valid trajectory starting from q, included in the ball of center q and radius , is such that the CoM is never over the left foot. Given the quasi-static walking conditions, the right foot of the robot is fixed along the trajectory. Thus, the set of accessible configurations from q by staying inside B(q, ) does not form a neighborhood of q, since it does not include any configuration where the right foot has moved. This shows that the robot is not small-space controllable.

Let us now consider a dynamically walking robot. Starting from any valid static configuration, the CoM can move vertically without affecting balance, so there is no need to consider this degree of freedom in the following. If the CoM is not over the edge of the support polygon, it is possible to move it in a quasi-static way inside a neighborhood of its current position that projects itself over the support polygon. It is thus sufficient and necessary to prove that for all > 0, it is possible to move the feet while keeping the CoM inside a neighborhood of size . Let such > 0 be arbitrarily fixed.

The model of a walking robot with a point mass at a fixed height is known in the literature as the cart-table model [START_REF] Kajita | Biped walking pattern generation by using preview control of zero-moment point[END_REF]. The equations giving the ZMP horizontal coordinates (p x , p y ) as functions of CoM horizontal coordinates (x, y) in the cart-table model were presented in [START_REF] Kajita | Biped walking pattern generation by using preview control of zero-moment point[END_REF]:

p x p y = x -zc g ẍ y -zc g ÿ (1)
where z c is the constant height of the CoM and g is the gravity constant. In the following we will note ω 0 = g zc .

Without loss of generality, let us assume that the robot is in a configuration in which the CoM is at the horizontal position (0, 0), the foot centers are aligned with the y-axis and the horizontal distance between the CoM and either of the foot centers is L. To achieve dynamically balanced walking, we aim at making p y (t) oscillate between -L and L. To move the ZMP under a given foot, only the y coordinate of the CoM is of interest. Thus, we will keep the x coordinates of the CoM and ZMP constant equal to 0. By hypothesis, the feet have a positive surface, let l > 0 be such that the length of the section of a foot along the y-axis is greater than l. Fig. 9 summarizes the notations used in the following. The idea of this proof is to use the form of Eq. ( 1) to apply a scaling factor between the amplitude of the oscillations of the CoM and of the ZMP. The faster the CoM oscillates, the bigger is the amplitude of the ZMP oscillations. Following is a formalization of this idea.

y-axis

CoM

For ω > 0, assuming the CoM follows the trajectory y(t) = sin(ωt), Eq. (1) gives:

p y (t) = (1 + ω ω 0 2 ) sin(ωt)
The amplitude of the oscillations of y is multiplied by a factor (1 + ω ω0 2

).

Choosing ω = ω 0 L -1 makes p y oscillate between -L and L, while y oscillates between -and . At time t

(n) l = n 2π ω + π/2
ω , the ZMP is located at the center of the left foot, the robot can move its right foot and at time t

(n) r = n 2π ω + 3π/2
ω the ZMP is located at the center of the right foot, the robot can move its left foot.

Starting from a static configuration at time (t = 0), we cannot apply directly a command y(t) = sin(ωt) because it generates a discontinuity in the speed of the CoM at time (t = 0). To overcome this discontinuity, we go through a transient state between (t = 0) and (t = T ) for some

T > 0. Let f : [0, T ] → [0, 1] be an increasing function of class C ∞ such that f (0) = 0, ḟ (0) = 0, f (T ) = 1, ḟ (T ) = 0 and f (T ) = 0.
We can explicitly construct such an f with a spline of degree 4. We also request that for all t ∈

[0, T ], |2 ḟ (t) ω ω 2 0 | ≤ l 4 and | f (t)/ω 2 0 | ≤ l 4
. These inequalities will be used to bound the trajectory of the ZMP. We can guarantee them by choosing T large enough. Let us now consider the following CoM motion:

y(t) = f (t) sin(ωt) if t ∈ [0, T ] sin(ωt) if t ≥ T
One can check that y is of class C 2 over R + , and that ḟ (0) = 0. When t ≥ T , the robot is in the permanent state described above and can successively move either of its feet inside small neighborhoods. The last point to check is that for t ∈ [0, T ] p y (t) stays inside the support polygon of the robot. The calculation of the successive derivatives of y gives:

p y (t) = f (t) (1 + ω ω0 2 ) sin(ωt) +2 ḟ (t) ω ω 2 0 cos(ωt) + ω 2 0 f (t) sin(ωt) For all t ∈ [0, T ], f (t) (1 + ω ω0
2 ) sin(ωt) lies between -L and L. The bounds on the derivatives of f guarantee that p y (t) lies between -L -l/2 and L + l/2, which means that the ZMP stays inside the support polygon. Fig. 10 shows an example of CoM motion on the y axis and the corresponding ZMP motion. Once in permanent in-place walking state, the robot can come back to a static state by applying a symmetric transient state used to decrease gradually the amplitude of the oscillations of the CoM without generating a discontinuity in the first derivative of the command.

We have thus exhibited a continuous control scheme that allows to move any of the feet in any direction, while keeping the CoM inside an arbitrarily small neighborhood. This concludes the proof.

Remarks

Generalization to a complete model: We did not extend the previous proof to any legged robot model since empirically, the table cart model is a very good fit for our humanoid robot. Although of little practical interest, the generalization of the proof does not seem very difficult to achieve. As an insight, the difference between the table cart model and the full size humanoid robot is due to the derivative of the angular momentum and to the vertical acceleration of the center of mass. These perturbations can be made as small as desired along the sliding path by following the sliding path as slowly as necessary. The derivatives of the angular momentum produced by the stepping motion can also be made as small as desired by making the step height as small as necessary and by using recent results on properties of joint trajectories induced by end-effector motions [START_REF] Zanchettin | A general user-oriented framework for holonomic redundancy resolution in robotic manipulators using task augmentation[END_REF].

Use of ZMP preview controller:

The control strategy presented in the previous proof may generate very long trajectories, because of the transient states at the beginning and end of the locomotion. In the actual implementation, we have chosen to generate CoM motions with a ZMP preview controller, as presented in [START_REF] Kajita | Biped walking pattern generation by using preview control of zero-moment point[END_REF]. We have observed experimentally that the amplitude of CoM trajectories decreases when the frequency of steps increases. Our current ZMP preview controller relies on the cart-table model approximation. To make this approximation valid, we fix the height of the robot CoM during walk, as well as the vertical orientation of the robot waist. These geometric constraints are also applied when planning statically balanced paths, to ensure that the paths can be approximated by dynamic walk trajectories. Note that this is due to our current ZMP preview controller implementation, and does not affect the generality of the small-space controllability result presented above.

Relying on the cart-table model approximation means that the angular momentum induced by arm movements for instance can lead to non dynamically balanced walking motion. We thus implement the ZMP filtering stage proposed in [START_REF] Kajita | Biped walking pattern generation by using preview control of zero-moment point[END_REF] to compute the exact ZMP, take into account the full dynamics of the robot and generate feasible trajectories.

Speed of CoM:

The theoretical result presented in this section implies that any collision-free path can be approximated by a sequence of admissible and collision-free trajectories. However, the theorem depends on a control law that generates trajectories with unbounded velocities for the CoM, when the input path is close to obstacles. The humanoid robot hardware may be a limitation to such trajectories. To prevent the generated CoM oscillations from being too fast, one has to require that the statically balanced path is included inside an -radius tube of the free space, where depends on the physical capacities of the robot.

Application: Dynamic Approximation of a Statically

Balanced Sliding Path

The algorithm that animates a statically balanced path into a dynamically balanced walk trajectory has been inspired by the previous small-space controllability proof. Given a statically balanced path p verifying the cart-table model approximation constraints, we start by placing footprints corresponding to the nominal walk pattern of the robot. Given the footprints, we compute a ZMP trajectory, derive foot trajectories, and a preview controller returns the corresponding CoM trajectory. Classic numerical Jacobian-based prioritized inverse kinematics methods prove to be very useful to generate a dynamic walking trajectory while trying to accomplish secondary tasks, such as following a reference configuration trajectory. We use the framework called Generalized inverse kinematics (Gik) and developed in [START_REF] Yoshida | Task-driven support polygon reshaping for humanoids[END_REF].

The hierarchy of tasks (referred to as GikTasks in Algorithm 4) applied to the robot to generate a dynamic walking motion is -in decreasing priority order: Tasks (1) and (2) generate a dynamically balanced motion by using the simplified cart-table model and the ZMP criterion. Tasks (3) and (4) ensure that the resulting motion is well described by the cart-table model. Task ( 5) is used to approximate p as well as possible given the walk parameters.

Because it comes at the lowest priority, task (5) is not necessarily fulfilled in the resulting trajectory. Hence, collisions may appear when animating p, if the resulting trajectory diverges too much from the initial sliding path. If so, it is necessary to approximate more closely p by a walk trajectory. To do so, we use the small-space controllability property of the system shown in the previous section. The way we use this property is inspired by similar results in non-holonomic mobile robot control presented in [START_REF] Laumond | A motion planner for nonholonomic mobile robots[END_REF].

If the animated trajectory collides with the environment, we cut the initial path p into two sub-paths, that we try to animate recursively. When the paths to animate are too short for the robot nominal walk parameters, we accelerate the steps, and decrease the maximum height of the moving foot. As shown in previous section, the walk trajectory corresponding to smaller and faster steps converges toward the sliding path. Algorithm 4 shows pseudo-code that takes a sliding path p as input and returns a collision-free walk trajectory

Experimental Results

The motion planning algorithms presented in this paper have been implemented using KineoWorks TM [START_REF] Laumond | Kineo CAM: a success story of motion planning algorithms[END_REF]. The planning times have been measured on an Intel Core 2 Duo 2.13 GHz PC with 2 GB of RAM. Evaluation of the randomized algorithm has been conducted by executing 500 trials on each scenario using two flavors of RRT: the classic RRT and IPP-RRT [START_REF] Ferre | An iterative diffusion algorithm for part disassembly[END_REF]). We present the results in Appendix A, Fig. 17, 18, 19, as well as in Extension 4 for the raw data.

Our whole-body motion planner generates a robot configuration trajectory that is sampled at a 200 Hz rate and stored in a file. This file can then be used to play the trajectory in open-loop on the HRP-2 robot, which is positioncontrolled. Scenarios in Sections 5.1 and 5.3 were both successfully executed.

To get more natural motions in the experiments, we require the foot positions to be fixed with respect to each other, and the CoM to be projected in the center of the support polygon during the sliding path planning stage.

Passing between two chairs

The environment shown in Fig. 1 and6 was presented in (El Khoury, Taix & Lamiraux 2011). There, the motion planning problem is solved with a bounding box method, leading the robot to walk sideways between the two chairs. Our method generates a locomotion trajectory in which the robot walks forward, which may be required if the robot has to use vision during locomotion. The first planning stage requires 1 s on average. The animation of the sliding path presented in Fig. 6 uses 66.5 s of computation time.

Walking among floating obstacles

'Put the ball on a shelf '

In the problem shown in Fig. 14 the robot has to put a ball on a shelf, in a constrained apartment environment. The final configuration is defined implicitly as a desired hand position. We have generated automatically goal configurations solving the task, as described in Section 3 . Then, we have applied our planner to generate a whole-body walking motion that solves the hand reaching task.

The solution sliding path is constrained between the table on the right and the lamp on the left. This passage is too narrow for the robot nominal walk parameters. When executing the walk motion resulting from our algorithm, the robot left hand is only a few centimeters away from the lamp.

The first planning stage requires 15 s on average, and the animation of the resulting walk motion presented in Fig. 14 requires around 190 s of computation time. Fig. 15 shows the robot CoM trajectory during locomotion. Extension 3 presents a comprehensive video of this problem, including the motion execution on the real robot HRP-2 on stage. Fig. 16 shows some snapshots taken from Extension 3.

Limits and Discussions

This section lists several limitations of the current methods, and discusses potential future work to overcome them.

Stepping over obstacles

Because of the kinematic constraints we apply at the planning stage, we are not able yet to plan motions where the robot steps over obstacles, while this is an important feature of humanoid robots. Nevertheless, because we compute Figure 14: Solution path for a hand reaching problem in an apartment. The goal is implicitly defined as an inverse kinematics task. collision queries on an exact model of the robot, our method is able to generate paths where obstacles pass between the feet of the robot. In future work, we plan to develop mixed methods, where collision avoidance at the leg level can be solved by footstep planning techniques, while whole-body collision-avoidance can be solved by the algorithm presented in this paper.

Environment representation

The experimental setup assumes perfect knowledge of the environment. This can be guaranteed during experiments by using calibrated objects and motion capture systems. This indeed allows us to focus on complex motion planning problems. The perception problem, interesting as it is, is thus completely decoupled from the planning problem in our presentation. From previous experiences however, we are confident that our algorithm will work as well in environments modeled by vision [START_REF] Nakhaei | Motion planning for humanoid robots in environments modeled by vision[END_REF][START_REF] Dang | Experiments on wholebody manipulation and locomotion with footstep real-time optimization[END_REF]).

Trajectory following

The setup also assumes perfect execution of the plan. It can be critical here, since non-nominal stepping may cause the robot to drift away from the planned trajectory. Future experiments will include trajectory following during plan execution.

Conclusion

In this paper, we have presented a simple algorithm for constrained motion planning and used it within a novel, well-grounded strategy for humanoid wholebody manipulation planning including locomotion. The locomotion algorithm is based on a formal small-space controllability property of humanoid robots. An important point is that this strategy only holds for dynamic walking robots, and not for quasi-static walking ones. We have used our motion planner on different challenging examples, and validated the generated motions on a real platform. We have discussed the limits and potential extensions of our method, and we plan to address them in future work.

A Sliding Motion Planning Benchmarks

B Index to Multimedia Extensions

Figure 2 :

 2 Figure 2: Random goal configurations solving a reaching task. All the configurations are balanced and collision-free, and the right hand of the character reaches the orange ball.

Figure 5 :

 5 Figure 5: HRP-2 grabs a ball on a shelf, puts it on another shelf, and comes back to a rest position. Static balance constraints are enforced along the path, and the intermediary goals consisting in grasping and displacing the ball are defined implicitly as inverse kinematics constraints.

Figure 6 :

 6 Figure 6: Collision-free statically balanced path for a humanoid robot sliding on the ground.

Figure 9 :

 9 Figure9: Simplified model of a legged robot. The CoM is at (0, 0, z c ), the two feet are flat on the ground, aligned with the y-axis, at a horizontal distance L from the CoM.

Figure 10 :

 10 Figure 10: CoM motion (solid line) along y axis. The CoM stays in the interval [-, ] while during permanent state (t ≥ T ), the ZMP (dashed line) oscillates between the centers of the feet, which allows in-place walk.

1.

  Positions and orientations of feet, 2. Horizontal position of the CoM, 3. Height of the CoM, 4. Verticality of the waist, 5. Configuration task towards corresponding configuration in p.

Figure 11 :

 11 Figure 11: Horizontal trajectory of the robot CoM during locomotion. When the robot is close to obstacles, the amplitude of the oscillations decreases.

Fig. 11

 11 Fig. 11 shows the horizontal trajectory of the robot CoM during locomotion. The amplitude of the oscillations decreases when passing between the chairs. This motion has been validated on a real HRP-2 platform. Extension 2 shows a video of the experiment.

Figure 12 :

 12 Figure 12: Solution path for a cluttered environment, the robot walks among floating obstacles.In the environment shown in Fig.12, the robot has to find a way among floating obstacles. In this environment neither bounding box nor footstep plan-

Figure 13 :

 13 Figure 13: Horizontal trajectory of the robot CoM during locomotion.

Figure 15 :

 15 Figure 15: Horizontal trajectory of the robot CoM during locomotion.

Figure 16 :

 16 Figure 16: Execution of the walking trajectory by HRP-2 on stage. The robot first goes to the shelves to release the ball, then comes back to a rest position.

Figure 17 :

 17 Figure 17: Number of RRT iterations it for the floating objects and the shelf scenarios, using two variants of RRT. Mean it, standard deviation σ it , minimum and maximum values are represented.

Figure 18 :

 18 Figure 18: RRT computation time t for the floating objects and the shelf scenarios, using two variants of RRT. Mean t, standard deviation σ t , minimum and maximum values are represented.

Figure 19 :

 19 Figure 19: Number of tree nodes n for the floating objects and the shelf scenarios, using two variants of RRT. Mean n, standard deviation σ n , minimum and maximum values are represented.

Table 1 :

 1 have run this set of motion planning problems 20 times; results are com-Experimental results on 20 runs: Each run consists of 3 motion planning problems and 2 goal generations for the three phases. Time is expressed in seconds.

		min	max average	average
					per problem
	number of nodes	43.00 481.00	102.70
	goal generation time (s)	1.00	1.56	1.22
	planning time (s)	67.36 376.84	134.28	44.76

  2 .

	Algorithm 4 FindDynamicTrajectory(Path p)
	F ootprints ← ComputeFootprints(p)
	GikT asks.addFootprintTask(F ootprints)
	GikT asks.addWaistTask()
	GikT asks.addConfigurationTask(p)
	DynamicT rajectory ← ComputeWalkTrajectory(GikT asks)
	if (CheckForCollisions(DynamicT rajectory) = Colliding) then
	(p 1 , p 2 ) ← CutInHalf(p)
	DT 1 ← FindDynamicTrajectory(p 1 )
	DT 2 ← FindDynamicTrajectory(p 2 )
	return Concatenate(DT 1 , DT 2 )
	else
	return DynamicT rajectory
	end if

This presentation attempts to give a precise idea of the algorithm, without focusing on technical details.Readers interested in the actual implementation can refer to https://github.com/laas/hpp-constrained and https://github.com/laas/ hpp-constrained-planner, where the corresponding open-source code is available.

The actual implementation of this algorithm is part of an open-source package, available at https://github.com/laas/hpp-wholebody-step-planner.

Acknowledgments

This work was supported by the French FUI Project ROMEO and the European Project ECHORD-231143. The authors would like to thank Thomas Moulard and Olivier Stasse for their valuable help during experiments.

Data

Raw data of sliding motion planning benchmarks for all scenarios.


Tobias Isenberg
email: isenberg@cs.rug.nl

Visual Abstraction and Stylisation of Maps

Keywords: Map stylization, generalization, abstraction, and simplification, illustrative rendering, non-photorealistic rendering (NPR)

We explore visual map abstraction for the generation of stylized renderings of 2D map data. We employ techniques that are centered around the concept of shape simplification and graph layout and that allow iterative abstraction of 2D maps. We use data from publicly available sources and show how we can iteratively generate aesthetic renditions of these maps. These renditions do not have the goal to allow for navigation tasks but instead show the map data in a distorted manner. The techniques used to create these images apply simplification, abstraction/generalization, and displacement operations to the map elements in varying orders and add stylistic shading to produce aesthetic renditions for print or electronic displays. The degree of abstraction/generalization can be individually chosen and determines the characteristics of the distorted map: whether components retain their shape, degenerate, or are processed in a manner that the abstraction becomes the focus of the image rather than the underlying map data. The renditions can be further personalized by choosing shading and colors for this shading. Together, the presented techniques allow for playful and creative exploration of aesthetic renditions of 2D map data.

INTRODUCTION

Cartography plays an important part in our daily lives [START_REF] Field | Editorial: 'Maps still matter -don't they?[END_REF][START_REF] Field | Editorial Preface: Art in C'art'ography[END_REF]-we use maps for many navigation tasks, both in abstract and in concrete domains. In particular geographic maps are frequently used, for example, in car navigation with a GPS device. Map creation has historically involved much artistry [START_REF] Field | Editorial Preface: Art in C'art'ography[END_REF])-from early cartographers who have created magnificent atlases to beautiful examples in modern interactive infographics. Even though some modern maps (e. g., in GPS car navigation) tend to focus on their task such as supporting navigation and only as a secondary aspect on their aesthetic character [START_REF] Kent | Aesthetics: A Lost Cause in Cartographic Theory[END_REF], artists have also explored maps in their works (e. g., [START_REF] Wood | Map Art[END_REF][START_REF] Varanka | Interpreting Map Art with a Perspective Learned from J.M. Blaut[END_REF][START_REF] Krygier | Jake Barton's Performance Maps: An Essay[END_REF][START_REF] Caquard | Editorial: Special Issue on Art & Cartography[END_REF][START_REF] Harmon | The Map as Art: Contemporary Artists Explore Cartography[END_REF][START_REF] Ljungberg | Cartographies of the Future: Julie Mehretu's Dynamic Charting of Fluid Spaces[END_REF][START_REF] Watson | Mapping and Contemporary Art[END_REF]); some art historians argue, for example, that Piet Mondrian, during the later part of his life, was at least in part inspired by maps or city street layouts to some of his well-known abstract works (Schoenholz Bee & Heliczer, 2004).

This study of abstraction of map data and its depiction, inspired by artworks and other sources, is the subject of this article. We are thus not interested in precise and correct depictions of the world but instead in altering maps to satisfy a specific personal aesthetic. 1 Traditionally, people have been using different types of abstraction for depicting map data, for instance to adapt the rendering to a chosen scale level or for highlighting particular aspects of the data. However, in these cases the depiction of map elements is typically driven by their original location,2 even though some elements may be depicted at sizes different from their actual ones. In this article we take a different approach: we explore the incremental generalization of geographic maps in terms of the location, orientation, and detail of map elements using several independent approaches (e. g., Figure 1). This exploration is based on real data and is made possible through freely available quality map data from on-line sources such as OpenStreetMap [START_REF] Coast | OpenStreetMap[END_REF]. In addition, we describe a way to depict the abstracted data as inspired by the Substrate simulation by [START_REF] Tarbell | Substrate. Web site and simulation[END_REF], a type of animated growth simulation (Figure 2). One could argue that the combination of both is a form of non-photorealistic and stylized map rendering,3 incorporating aspects of generalization/abstraction as well as artistic depiction. The application domain for this work is certainly not the precise and correct cartography (possibly with an aesthetic appeal) of a part of the world but instead the artistic and creative play with the abstraction of map data. 4 We see our contribution, instead, in the exploration of the creative interpretation of a map generalization process using visual map abstraction. We have implemented only some possibilities in this context and there are many variables to tune and adjust, but this freedom also brings with it the possibility to interactively explore these options. People may create, for example, aesthetic depictions of neighborhoods they are familiar with or places they would like to go. Potential other applications lie in generating imagery for electronic picture frames or personal print material such as increasingly popular photo books, for example about a family vacation.

The remainder of the article is structured as follows. First, we survey related work with respect to previous approaches to shape abstraction as well as some specific inspirations. Next, we introduce the em-ployed abstraction techniques and explain the rendering of the resulting data. Then, we give a number of details about the realization of the technique, show more results, and mention limitations. The article concludes with a summary and a discussion of potential future work.

RELATED WORK

Research related to our own work can be found in several domains: in the computer graphics sub-domain of non-photorealistic rendering (NPR), generally in abstract styles of depiction (e. g., for visualization), in shape simplification for 3D shape representations, in gesture recognition, in information visualization, and in certain forms of computer art. We briefly discuss these connections in the following paragraphs.

In NPR we can find several approaches that exchange detail on small scales with image or geometry objects on larger scales to achieve abstraction. Examples are techniques within stroke-based rendering [START_REF] Hertzmann | A Survey of Stroke-Based Rendering[END_REF] including, e. g., watercolor rendering [START_REF] Curtis | Computer-Generated Watercolor[END_REF] or image mosaics [START_REF] Hausner | Simulating Decorative Mosaics[END_REF] where this exchange happens by sampling the original image on a different scale. Other examples include approaches that detect (groups of) detail objects and replace them with abstracted objects using dedicated processes (e. g., [START_REF] Bousseau | Interactive Watercolor Rendering with Temporal Coherence and Abstraction[END_REF][START_REF] Coconu | Real-Time Pen-and-Ink Illustration of Landscapes[END_REF][START_REF] Decarlo | Stylization and Abstraction of Photographs[END_REF][START_REF] Luft | Real-Time Watercolor Illustrations of Plants Using a Blurred Depth Test[END_REF][START_REF] Mehra | Abstraction of Man-Made Shapes[END_REF]).

The techniques discussed in this article are inspired by previous work in computer graphics that specifically addresses the abstraction, generalization, and simplification of shape. In particular it relates to the work by [START_REF] Mi | Abstraction of 2D Shapes in Terms of Parts[END_REF] who describe an approach to abstract 2D shapes in terms of their parts. They, in fact, distinguish between earlier approaches to shape simplification on the one side which iteratively remove detail on a small scale and techniques for shape abstraction on the other which try to recognize parts on larger scales such as their method. Mi et al.'s shape abstraction technique is well suited, in particular, to map shapes as the authors demonstrate. Specifically, Mi et al. show how outlines of islands and continents (along with other objects) can be abstracted because these can be thought of as areal shapes with outlines so that relations such as 'part of' are defined. However, it is not clear how to apply them to general 2D map representations as used in our work which largely consist of a graph of connected line segments where a 'part of' relation cannot as easily be defined. Instead, the mesh simplification techniques to which Mi et al. compare their approach (e. g., [START_REF] Ramer | An Iterative Procedure for the Polygonal Approximation of Plane Curves[END_REF][START_REF] Douglas | Algorithms for the Reduction of the Number of Points Required to Represent a Digitized Line or Its Caricature[END_REF][START_REF] Hoppe | Progressive Meshes[END_REF][START_REF] Garland | Surface Simplification Using QuadricError Metrics[END_REF]) and similar techniques (e. g., [START_REF] Visvalingam | Line Generalisation by Repeated Elimination of Points[END_REF][START_REF] Zhou | Shape-Aware Line Generalisation With Weighted Effective Area[END_REF]) are better suited in our context as they do not require information beyond connected edges in a graph and an error metric. Such algorithms have long been used for processing map data and many are implemented in GIS tools (e. g., MapShaper 5 (Bloch & Harrower, 2006;Harrower & Bloch, 2006)).

A related form of shape abstraction/generalization focusing on connected line segments can be found in gesture recognition. Here, the task is to match samples from usually hand-drawn stroke shapes to previously recorded or defined archetypical (i. e., abstracted) ones. Thus, the processing of gestures for recognition also requires a generalization step in order to be able to compare a newly performed gesture stroke to a known stroke. Noteworthy in this context is, e. g., the $1 Gesture Recognizer by [START_REF] Wobbrock | Gestures Without Libraries, Toolkits or Training: A $1 Recognizer for User Interface Prototypes[END_REF] which provides a relatively simple way to recognize gestures in a sampling-, rotation-, size-, and location-invariant manner. It is based on resampling, rotating, and path-matching the input strokes to derive quality measures of the match for the collection of pre-recorded templates.

Abstraction and selective detail for maps related to our visual map abstraction has previously been explored in some techniques, often aimed at navigation tasks. For example, [START_REF] Agrawala | Rendering Effective Route Maps: Improving Usability Through Generalization[END_REF] describe how to render effective route maps by generalizing different sections of route descriptions to different degrees, guided by cognitive psychology and common use cases of these maps. Related is the approach by Böttger et al. (2008a,b) who warp real geographic maps such that they can be overlaid on abstracted maps that show public transportation systems (e. g., metro maps). Another example is pre-5 See http://www.mapshaper.org/ . [START_REF] Tarbell | Substrate. Web site and simulation[END_REF].6 sented by [START_REF] Grabler | Automatic Generation of Tourist Maps[END_REF] who show how to generate abstracted tourist maps that emphasize the most important elements. Related to these navigation-focused methods are also information visualization techniques that distort maps such that additional data attributes can be shown (Brinton, 1939, Chapter 29). For example, [START_REF] Panse | Visualization of Geo-spatial Point Sets via Global Shape Transformation and Local Pixel Placement[END_REF] display geo-spatial point set data on maps that are distorted using a global shape function while [START_REF] Dorling | Worldmapper: The World as You've Never Seen it Before[END_REF] represent information that records data by territory on distorted maps on which the territories were resized accordingly. Approaches such as these abstract from the original spatial shape of maps to varying degrees but with the intention of conveying information rather than (primarily) aesthetics. Beautiful historical maps, however, often contain (intentional or unintentional) geographic distortions as analyzed by [START_REF] Jenny | Studying Cartographic Heritage: Analysis and Visualization of Geometric Distortions[END_REF], and this geographic distortion can be an aspect of the map's aesthetics.

Finally, the specific visual inspiration for this article largely comes from [START_REF] Tarbell | Substrate. Web site and simulation[END_REF] Substrate simulation (see an example in Figure 2). 6 This simulation spawns paths at various locations of the screen that are extended over the canvas as long as they do not hit an existing path. These paths are simple geometric primitives such as straight lines or parts of ellipsoids, and are complemented with watercolor-like shaded lines that radiate out perpendicular from the main paths. This results in depictions that have an appearance of abstracted cities and country-side between them, and led to the idea of replicating similar depictions but based on real map data.

MAP GRAPH ABSTRACTION/GENERALIZATION

Abstraction plays an important role in map making [START_REF] Robinson | Elements of Cartography[END_REF]. Cartographers employ many forms of generalization and simplification, both of the core spatial information as well as of the additional data shown on maps. For example, streets are typically shown wider than the map's scale requires and smaller features are omitted in larger-scale maps. For some mapping purposes (e. g., thematic maps) the cartographer may even introduce more simplification than technically necessary for the chosen scale. Most of these abstraction techniques are applied in cartography due to the technical limitations of scale and/or to promote understanding [START_REF] Robinson | Elements of Cartography[END_REF].

In this work, however, we are interested in a visual abstraction or generalization of maps that goes beyond what is technically necessary for the creation of effective maps. Our approach is driven by (personal) aesthetics rather than a need for using maps for navigation tasks. For this purpose and based on map data available from OpenStreetMap [START_REF] Coast | OpenStreetMap[END_REF], we describe a set of abstraction and simplification techniques that, in part, are inspired by the Substrate simulation as intro- [START_REF] Coast | OpenStreetMap[END_REF] and filtered set of lines for the employed example map section (Schiermonnikoog island in the Netherlands).

duced above. These techniques can be applied independently of each other and in various sequences, each resulting in a different visual abstraction of the original map.

For these techniques we assume the map data to be available in form of an undirected graph of connected edges that, in our specific implementation, is extracted from the downloaded OpenStreetMap data, details of which are provided in Section 5. For the purpose of describing the technical details we use an example map of Schiermonnikoog, one of the Dutch islands in the North Sea shown in Figure 3. This particular map section was selected because it is relatively simple, has both low-detail and high-detail areas, and also contains a number of small and large loops of edges (e. g., the shore).

For achieving our goal of map abstraction we require techniques that are capable of generalizing graph data that consists of connected polylines, as opposed to polygons that have an inside and an outside such as used by [START_REF] Mi | Abstraction of 2D Shapes in Terms of Parts[END_REF]. As a second constraint we require the abstraction techniques to produce a sequence of simple local generalization steps that first remove small details before introducing larger changes. Thus, the sequence has to be ordered with respect to the degree of modification in order to be able to steadily increase the level of abstraction. Finally, we aim to achieve a general visual abstraction rather than an abstraction or generalization that satisfies qualitative or quantitative criteria with respect to understandability. That means that not only generalization techniques that reduce the number of map edges are suitable for our purpose but also those that instead appropriately change the location of these edges.

Below we describe a number of such techniques that we selected according to the mentioned criteria and which are mostly borrowed from other domains or which are relatively straightforward methods. As they are described in detail elsewhere we keep the description brief and focus on possibly necessary adaptations to the above requirements and on the application to the specific problem of map data abstraction.

Progressive Mesh Technique

The first technique we examined-progressive meshes [START_REF] Hoppe | Progressive Meshes[END_REF][START_REF] Garland | Surface Simplification Using QuadricError Metrics[END_REF]-is borrowed from 3D surface mesh simplification. It works by computing an error metric that determines the potential error that would be introduced by collapsing a given edge in the mesh. In each step of the algorithm, it selects the edge whose deletion would introduce the smallest error and then collapses it. During an edge collapse, adjacent edges are affected, some other edges may also be removed, and the changed potential error for all changed edges is computed. By iterating this process one can compute an increasingly simplified version of the original mesh, until no further iterations are possible or the mesh starts to degenerate.

We apply the same technique to map graphs (similar to what Mi et al. ( 2009) did for the comparison of different shape generalization techniques), differing from the original progressive mesh technique [START_REF] Hoppe | Progressive Meshes[END_REF][START_REF] Garland | Surface Simplification Using QuadricError Metrics[END_REF] only in that our map 'meshes' may also contain vertices with a degree of < 3. The error metric we employ is the length of the edges so that shorter edges are collapsed first (other error metrics can easily be substituted). In addition, for computational reasons (one would have to re-sort the edge list in every step) we use the simplification that we only re-compute edge lengths and re-sort the edge list after N edge collapse operations. We start with N = 40 when the graph contains more than 1500 edges and reduce N in steps down to 1 for graphs with 300 edges or less.

The result of applying this technique to the example map is shown in Figure 4. We see that local features are removed while the resulting lines, in part, contain some roughness due to sharp corners. For creating Figure 4 we used additional constraints in form of pinning down vertices in the map graph such as ends of ways or vertices of degree > 2 (i. e., intersections). This prevents the algorithm from removing meaningful features such as detail within cities and towns.

Force-Directed Technique

Force-directed algorithms have long been used to achieve graph layouts that are aesthetically pleasing [START_REF] Di Battista | Graph Drawing: Algorithms for the Visualization of Graphs[END_REF] by minimizing the 'energy' in a graph. Nodes are laid out by iteratively applying forces and, thus, moving the vertices in a graph based on their previous positions and possibly external constraints. In graph drawing, force-directed techniques are often employed to compute the layout for highly connected graphs, while our map graphs often have long chains of edges that represent boundaries or ways. In this context one could say that the application of a force-directed technique removes noise from the chains of edges, resulting in a more abstract representation that we are interested in.

Specifically, we start from a specific map graph layout and compute offsets for all nodes of the graph based on the location of their direct neighbors. To derive the offset for a node, we add up the the vectors to each of its direct neighbors, multiplied by a factor (we use 0.25). This results in a gentle smoothing of the map (see Figure 5) and a general contraction. To reduce the latter we can introduce similar constraints as done in Section 3.1 by pinning down certain vertices.

Orthogonalization Technique

Inspired by Piet Mondrian's abstract paintings with orthogonal lines, we also explored a special form of force-directed layout that aims to turn all edges toward that coordinate axis for which the angle between edge and coordinate axis is smallest (Figure 6). We achieve this by adding offsets to the vertices of each edge that turn it horizontally or vertically, rotating it around its center. While this would immediately 'orthogonalize' an independent edge, it is an iterative process in the case of a connected graph as connected edges influence each other. To simplify computation and due to this interaction of connected edges, we can employ a simpler computation for each edge: we simply use one half of the amount of the horizontal or vertical extent (whichever is smaller) of the edge as an offset (this can be computed as the dot product of the edge vector with a horizontal or vertical unit vector), directed to align the edge with the closer coordinate axis. While this approach turns non-connected edges horizontal or vertical in one step, it also introduces occasional oscillations for some edges with constrains from the connectivity in the graph. Therefore, we reduce the mentioned factor from 0.5 to 0.35 which leads to a slower convergence but also avoids oscillations.

The result of this technique is shown in Figure 6 (after an initial application of progressive meshes). An interesting effect is the behavior of long chains of small edges that are all close to horizontal (such as at the Northern coast of the island in the example) or vertical: these slowly propagate the horizontal or vertical property along the chain but do not converge to a fully horizontal or vertical line within a reasonable number of iterations (about 1 min of running).

Ramer-Douglas-Peucker Technique

Another goal for the abstraction of map graphs could be to attempt to replace long chains of edges (ways) with simpler representations of these. A way consists of a polyline in the graph for which all connector nodes have a degree of two; thus ways connect nodes of degree one (ends) or more than two (intersections). For this purpose we employ the Ramer-Douglas-Peucker algorithm [START_REF] Ramer | An Iterative Procedure for the Polygonal Approximation of Plane Curves[END_REF][START_REF] Douglas | Algorithms for the Reduction of the Number of Points Required to Represent a Digitized Line or Its Caricature[END_REF] which, in its original form, computes polyline simplification backwards: the technique starts with the most abstract form of a polyline-one edge that connects the first and the last point. It then proceeds to add detail by searching for the vertex farthest from the connecting edge and adding a new vertex at this location in the middle of the initial edge. The algorithm proceeds by recursively treating the two newly created smaller edges. There are three issues with this original approach: (1) it computes the abstraction backwards (from abstract to detailed rather than from detailed to abstract as we need it), (2) it also does not provide a linear order of the abstraction steps due to its hierarchical design, and (3) it computes the abstraction by individual polyline/way and not for the entire maps as we need it. Thus, we adapt the original technique to address these issues as follows (see the pseudocode in Listing 1).

First, we compute the Ramer-Douglas-Peucker abstraction hierarchy as in the original algorithm. For each stepping out of a recursion, however, we adjust the technique by merging the abstraction steps (i. e., point collapse operations) from both recursions. This merging is done such that we always take the point collapse operation with a lower error (i. e., point distance from abstract edge) first but that the order within each series of abstraction steps is maintained. This ensures that, for any set of possible point collapse operations, the algorithm chooses the one that introduces the lowest error. After each merging, we add the point collapse operation between the two parts as the last operation to the list. This makes sure that the order of abstraction is reversed to 'from detailed to abstract.' Finally, for each newly computed list of point collapse operations (one for each way) we merge this with the already existing list from previously treated polylines the same way as the merging occurs in the recursion, again ensuring that for all possible next point collapse operations the one with the least error is chosen.

The result of applying this technique for the example map is shown in Figure 7. Similarly to the progressive mesh technique it abstracts the map graph resulting in a more polygonal shape, but does preserve some local features over more iterations (note the differences between Figures 4 and7; both abstracted maps use the same number of edges).

Visvalingam-Whyatt Technique

As a final polyline generalization technique we examined Visvalingam-Whyatt algorithm [START_REF] Visvalingam | Line Generalisation by Repeated Elimination of Points[END_REF], being another method frequently used in map generalization (Bloch & Harrower, 2006). It examines the potential areal displacement that would be introduced by removing a node from one of the polylines and then picks that node to collapse that introduces the lowest areal displacement. Figure 8 shows a result of the application of this technique.

RENDERING OF THE ABSTRACTION/GENERALIZATION

For rendering the abstracted maps we take inspiration from [START_REF] Tarbell | Substrate. Web site and simulation[END_REF] previously mentioned Substrate simulation (Figure 2). It employs densely drawn colored lines, placed perpendicular to the main (black) lines on one of its sides. These lines have a length that varies randomly and they fade out toward the end. This creates an effect that is reminiscent of watercolor painting and we strive to render our abstracted maps in a similar way.

For this purpose we use each line in the map graph and turn it by 90°(see the schematic illustration in Figure 9). We compute a scaling factor that comprises a constant part (we use 40% of the original edge length) and a random part (up to 30% of the original edge length) and scale the turned line with it. We then draw colored lines with the computed length emerging perpendicularly from the graph edge where each starting point is separated from the next by one pixel. This general approach has the effect that for longer edges in the original map graph also wider colored patches are created. While the chosen percentages (colored lines being shorter than the original edges by 30-60%) typically limit the overlap of color patches and other lines, sometimes the overlap is too large. This happens, in particular, when the distribution of edge lengths in the map graph is uneven. Thus we introduce a user-specified maximum length for the colored edges.

The colors are randomly chosen from a palette with one color for all lines originating from a map graph edge. In addition, the colored lines have a given transparency at their start (we use approx. 60%) which is linearly increased to 100% at their ends, resulting in a fading out and visual shortening effect. Inspired by the colors chosen for the Substrate simulation (which in turn were inspired by colors used by Jackson Pollock [START_REF] Tarbell | Substrate. Web site and simulation[END_REF]) we use a similar color palette (e. g., Figures 1,10,13 and 15). Alternatively, we explored color palettes from ColorBrewer [START_REF] Harrower | ColorBrewer.org: An Online Tool for Selecting Color Schemes for Maps[END_REF][START_REF] Brewer | ColorBrewer 2.0[END_REF]) (e. g., Figure 11), the use of one single color for all colored edges (e. g., Figure 12), or a palette with randomly chosen colors.

REALIZATION

The implementation of the discussed techniques was done in Java and Processing. The Processing library7 was chosen for its support of various rendering engines and export facilities while Java is used mostly for providing the UI elements to control the application of the algorithms. To internally represent the map graph data we employ the [START_REF] Harrower | ColorBrewer.org: An Online Tool for Selecting Color Schemes for Maps[END_REF][START_REF] Brewer | ColorBrewer 2.0[END_REF]. Notice the different widths of colored patches due to the different lengths of the map graph edges.

Figure 12. Abstracted map from Figure 7 with a single color and limiting the length of color edges to approx. 30 pixels.

Jung library. 8 The resulting images are either exported to PDF (for lines only) or to PNG (for color images) through Processing's export facilities. The reason that color images are not exported to a vector format is that an interpolation of transparency along a line is not supported by Processing's PDF or SVG output.

The data is derived from OpenStreetMap [START_REF] Coast | OpenStreetMap[END_REF]) through their data export module which allows to extract a map section and save it as an XML file. These files are read in using Processing's XML import module or obtained directly through an on-line query using OpenStreetMap's Web API, and are stored in the Jung data structure. We filter this data so that we can concentrate on the most relevant map 8 Jung stands for the Java Universal Network/Graph Framework; see http://jung.sourceforge.net/ . features. For example, single vertices (such as points of interest) and certain line features (e. g., administrative boundaries, city limits, etc.) can be removed from the data to be visualized.

As some operations can be quite time-consuming, we employ several measures to speed up the processing. This includes the previously mentioned re-sorting only after a number of steps which was done for the progressive mesh technique. In addition, we also make sure that we only compute data when necessary. For example, we compute the simplification sequence for the Ramer-Douglas-Peucker technique only once for subsequent abstraction steps and only invalidate it when a different technique is applied. The result is that all techniques can be applied interactively and we even have to introduce wait cycles because otherwise the simplification of graphs with only few meshes happens too fast to be able to stop it when desired. For the example map (2086 initial edges) we compute 69 force-directed iterations and 97 orthogonalization iterations per second, while in the first second of computing we perform approx. 304 and 650 iterations for the progressive mesh and the Ramer-Douglas-Peucker technique, respectively (the last two values change over time as the graph is simplified). All measurements were made using full rendering on a 3 GHz Intel ® Core ™ 2 Extreme CPU running Windows Vista. Larger maps (i. e., more vertices) such as shown in Figures 14-15 may lead to fewer iterations per second.

RESULTS

Both the map graph simplification/generalization and the choice of rendering technique add to the abstraction of map data. The rendering of lines within the map as simple black lines removes much of the information such as type or importance of its associated map element. In addition, the shading emphasizes the polygonal nature of the elements. While this works well together with the map graph simplification techniques it is not even always necessary to apply them as shown in The simplification and abstraction techniques for the map graph seem to work best when there are fewer nodes with high degree. For example, in city centers (e. g., Manhattan in Figure 14) there are many street intersections connected by straight streets (i. e., only one edge between two intersections). In this case it is more difficult for both the simplification techniques (progressive meshes and Ramer-Douglas-Peucker) and the force-directed techniques to introduce changes that have an abstracting or generalizing effect without degenerating the map graph. In contrast, in regions with longer edge chains and, thus, fewer intersections abstracting changes are easier to introduce (e. g., Central Park in Manhattan in Figure 14, rural areas such as the example from Europe in Figure 15, the river banks shown in Figure 16, or the man-made island "Palm Jumeirah" simplified using the Ramer-Douglas-Peucker technique in Figure 1).

The abstractions that result from the proposed techniques (when color patches are added as described) are reminiscent, to some degree, of artworks from the Cubism movement as well as NPR techniques inspired by Cubism such as the one presented by [START_REF] Collomosse | Cubist Style Rendering from Photographs[END_REF]. This is due to the reduction to simple polygonal shapes which are emphasized by the color patches, reminiscent of the basic geometric shapes that are an important aspect in Cubist artworks.

LIMITATIONS AND POSSIBLE EXTENSIONS

There are a number of limitations of the current implementation that should be noted. Some of these limitations arise from the treatment of the map as a simple graph of connected polylines and it being derived from OpenStreetMap. For example, it is currently not possible to consistently apply shading only to, for example, the land side of coastlines, lakes, or islands. While it would be possible to derive the information necessary for this behavior for closed polygons based on the type of the element, it is not guaranteed that map elements such as islands are represented as a single, closed polygon. Therefore, the shading is currently being placed always on the same side of the sequence of vertices in the data. An alternative, of course, would be to apply colored shading to both sides of a polyline. We did not choose to do so in order to retain the Substrate aesthetics and because shading on both sides would reduce the contrast of the depicted elements.

Another problem arises from the labeling of elements with multiple attributes-not all map elements work well in our approach (for example, we are currently omitting elements such as political boundaries). However, some polylines in the data are used for multiple purposes, which sometimes results in complex filtering configurations being necessary-this has not yet been implemented to a satisfying degree. Moreover, the use of OpenStreetMap's Web API for loading on-line data imposes restrictions: the API only allows the loading of maps that cover a relatively small area. However, even if larger areas could be loaded, the sheer amount of data would likely prohibit its processing within a reasonable time. Therefore, for being able to explore maps such as the boundaries of countries or the shape of the continents it would be necessary to add filtering when loading data from the database. If that were possible, it would also be interesting to explore the application of generalization techniques that do require an inside and an outside of elements (such as the one by [START_REF] Mi | Abstraction of 2D Shapes in Terms of Parts[END_REF]), in addition to exploring additional generalization algorithms (e. g., a weighted Visvalingam-Whyatt algorithm [START_REF] Zhou | Shape-Aware Line Generalisation With Weighted Effective Area[END_REF]).

In the future it will also be interesting to explore the use of other types of maps such as subway maps as well as the application to 2D shapes other than maps such as general vector data or graphs. In addition, for the currently employed maps we plan to further explore filtering as some elements may be suitable for one location while not as much for others. In this context it would also be interesting to add point data and explore their visual abstractions, e. g., in the form of point clouds. Also, we want to pursue other forms of abstraction such as the fitting of simple shapes such as circles or ellipsoids to polylines. Finally, an evaluation of the approach with people could inform a future development of the tool and/or the types of uses the presented techniques may have.

CONCLUSION

In this article we have explored techniques to visually abstract map graphs with the goal of producing aesthetic renditions of the data, distorting the context of map elements. This abstraction is visually inspired by the existing Substrate algorithm but realizes a similar aesthetic based on map data from OpenStreetMap. One may argue that the original Substrate simulation already produces map-like images, but the specific goal of this work is to produce images in a style inspired by Substrate but based on real maps that are chosen by the person interacting with the tool and with that person having control over the process-rather than completely controlled by the Substrate algorithm. Therefore, our contribution lies in enabling such interactive exploration of the abstraction process using a number of largely wellknown techniques, and applying them to the specific case of map generalization. Specifically, we discussed how to generalize map graphs, how to affect the location of map graph edges, and how to render the resulting abstractions. The explorative interaction with the resulting tool involves controlling a large number of unknowns, which at the same time opens up plenty of possibilities to explore these unknowns. For example, when one applies map graph simplification, it is the specific order and number of steps that are applied for each of the different techniques as well as the chosen visualization that heavily influence the resulting abstraction. The aesthetic appeal of the produced images, consequently, is in the eye of the beholder and people other than the creator of the image may like it or not. We envision applications in the realm of ambient visualization with possibly additional data being displayed on abstracted or non-abstracted map displays. An on-line tool (e. g., similar to MapShaper (Bloch & Harrower, 2006;Harrower & Bloch, 2006)) would also offer the possibility for people to explore their own map data and to create renditions for personal use. Such an on-line tool could easily be created in the future based on the existing Java implementation and could also serve as an informed sandbox for exploring map abstraction designs.

Figure 1 .

 1 Figure 1. Visual map generalization/abstraction using the example of a map showing Dubai's Palm Jumeirah.

Figure 2 .

 2 Figure2. Screen capture of a Substrate simulation[START_REF] Tarbell | Substrate. Web site and simulation[END_REF].6

Figure 3 .

 3 Figure3. Map from OpenStreetMap[START_REF] Coast | OpenStreetMap[END_REF] and filtered set of lines for the employed example map section (Schiermonnikoog island in the Netherlands).

Figure 4 .

 4 Figure 4. Map from Figure 3 after simplification from 2086 edges to 452 edges using progressive meshes, with intersections and end nodes pinned to their original locations.

Figure 5 .

 5 Figure 5. Map from Figure 3 after 134 iterations of the force-directed technique.

Figure 6 .

 6 Figure 6. Map from Figure 3 (first simplified without restrictions using progressive meshes to 658 edges), after 555 iterations of the rectangularization technique.

  ALGORITHM : Simplify using Ramer -Douglas -Peucker INPUT : array of nodes N, empty array of distances D OUTPUT : array of nodes is updated with correct order void simplifyRDP ( nodes N, distances D) { // find index of node furthest from the baseline int furthest = findNodeFurthestFromBaseline (N); node furthestN = N[ furthest ]; float distance = nodeDistanceFromBaseline (N, furthest ); // recursively simplify sections before and after nodes N1 = N. subArray (0, furthest -1); distances D1 = D. subArray (0, furthest -1); simplifyRDP (N1 , D1 ); nodes N2 = N. subArray ( furthest +1, N.size () -1); distances D2 = D. subArray ( furthest +1, N.size () -1); simplifyRDP (N2 , D2 ); // merge simplification steps from the two parts // before adding the simplification step of this // level of the recursion int i1 = 0, i2 = 0, i = 0; while ( (i1 < N1.size ()) || (i2 < N2.size ()) ) { // in case we already copied all of D1 & N1 // copy rest of D2 & N2 if (i1 >= N1.size ()) { D[i] = D2[i2 ]; N[i] = N2[i2 ]; i++; i2 ++; } // or in case we already copied all of D2 & N2 // copy rest of D1 & N1 else if (i2 >= N2.size ()) { D[i] = D1[i1 ]; N[i] = N1[i1 ]; i++; add the simplification step of this // recursion level at the end of the sequence D[i] = distance ; N[i] = furthestN ; // N & D are now updated to the correct sequence } Listing 1. Pseudocode for reversing the output of the Ramer-Douglas-Peucker polyline simplification into a sequence from detailed to abstract.

Figure 7 .

 7 Figure 7. Map from Figure 3 after simplification with the Ramer-Douglas-Peucker technique to 452 edges.

Figure 8 .

 8 Figure 8. Map from Figure 3 after simplification with the Visvalingam-Whyatt technique to 452 edges.

Figure 9 .

 9 Figure 9. Schematic depiction of how the colored lines (blue) are cre-with respect to the base line from the map graph (black). In practice the colored lines are placed much denser and fade out toward their ends to create the appearance of colored patches.

Figure 10 .

 10 Figure 10. Abstracted map from Figure 4 with Substrate-inspired colors.

Figure 11 .

 11 Figure 11. Abstracted map from Figure 6 with pastel color map from ColorBrewer[START_REF] Harrower | ColorBrewer.org: An Online Tool for Selecting Color Schemes for Maps[END_REF][START_REF] Brewer | ColorBrewer 2.0[END_REF]. Notice the different widths of colored patches due to the different lengths of the map graph edges.

Figure 13 .

 13 Figure 13. The center of Paris with Île de la Cité, without any simplification/abstraction applied to the map graph.

  Figure 13. Here, a part of Paris is shown with only the rendering applied and without any additional map graph simplification.

Figure 14 .

 14 Figure 14. Manhattan with Central Park, simplified with Ramer-Douglas-Peucker to about ½ of the original edge count.

Figure 15 .

 15 Figure 15. A rural area in Europe, after processing with the Ramer-Douglas-Peucker technique and orthogonalization, without pinning any vertices.

  (a) Before generalization (4579 edges). (b) After generalization, with shading (395 edges).

Figure 16 .

 16 Figure 16. A river section in Asia abstracted with the force-directed technique and Ramer-Douglas-Peucker.

The term "personal," here, does not refer to the article's authors but to the people working with the map generalization approach described in the article.

An exception may be seen, e. g., in the heavily abstracting visualization of driving directions by[START_REF] Agrawala | Rendering Effective Route Maps: Improving Usability Through Generalization[END_REF] or typical subway maps (see, e. g., the recent essay on subway map design by[START_REF] Roberts | Henry Beck Rules, not OK? Breaking the Rules of Diagrammatic Map Design[END_REF]).

It is not clear, however, what a photorealistic map rendering would look like (other than a satellite image) since maps inherently incorporate abstraction.

We realize that the duality of art and science is being discussed for cartography[START_REF] Krygier | Cartography as an Art and a Science?[END_REF] but this article does not intend to answer this question.

See http://www.complexification.net/gallery/machines/substrate/ , the simulation was also ported as a style to the Linux screensaver "XScreenSaver."

An extension of Java, see http://processing.org/ .

ACKNOWLEDGMENTS

We would like to thank Henk Bekker, Maarten H. Everts, Moritz Gerl, Petra Isenberg, and Ross Maciejewski for inspiring discussions on the topic and many suggestions for improvement as well as Jason Dykes for valuable comments on an earlier version of the article.

A DEMO PROGRAM

The Java program used to create the images shown in the article can be accessed via Java Webstart at http://osmabstraction.isenberg.cc/ and can be run on Windows, Linux, MacOS X, and other platforms that provide a Java Runtime Environment (JRE). The program does not only support the loading of map data files that were downloaded from the OpenStreetMap website but can also directly access the Open-StreetMap data through the OSM Web API.