Fanny Coulomb, Liliane Bensahel, Jacques Fontanel, Economists' controversies about the causality between war and economic cycles. Frontiers of peace economics and peace science, Editors Chatterji, M., Chen Bo, Missra, R. Contributions to Conflict Management, peace economics and dévelopment, Vol. 16, Emerald, 2011.

The issue of the link between wars and economic cycles and of the sense of the causality has given rise to many economic studies. The statistical works of N.D. Kondratiev1 in the 1930s, showing the existence of long economic cycles regulating capitalism, have much contributed to the economic cycles' theory. This analysis based on the observation of long-term economic changes in GDP growth rates and/or price levels, allows showing some rising and declining phases, as well as reversal points of the cycles. Among the most easily identifiable phenomena is the economic crisis of the 1930s, the post Second World war growth period, or the economic crisis started in the 1970s. However, as shown by a study of Andrew Tylecote2 , the long economic cycles are less identifiable for the 1850-1930 period, unless the disruptive effects of the American civil war and of World War I are considered: their recessive then reflationary effects would have disrupted the rising and declining phases. But some analyses present the war as being a central factor in long-term economic changes. G. Modelski3 's theory of long cycles has become very famous in the 1980s. It identifies cycles of 100-120 years, starting with an exceptionally long global war (it may also be a more discontinuous phase of war, like the two world wars), and giving rise to a new dominant power. Its technological and commercial domination permits to keep an uncontested supremacy, until some competing powers start to erode it. However, this theory does not focus on the links between major wars and long-term economic changes.

This issue having been largely studied in the past, the first part of the paper will present a review of these analyses. It will then in a second part be asked if these ideas may help predicting future major economic crises and related international conflicts. It's a delicate task, as it is as difficult to show subsequently a link between economic cycles and major wars as to predict future cyclical phenomena on the world economic and political scene.

I -The various aspects of the link between economic cycles and wars

The economic studies underline two contradictory effects of wars, reflationary and recessive. From the 1920s, the cycles' analysis presents a new type of explanation, showing a relation between the outbreak of major conflicts and certain phases of long economic cycles.

I.1. War as an outcome of a long phase of economic growth

The statistical studies of N.D. Kondratiev show long cycles of forty or sixty years, regulating the capitalist economies. The cycles and consequently the economic crises are presented as elements of the complex capitalist economic system's process. Kondratiev 4 has included wars and civil unrest in his analysis: the periods of economic expansion of advanced capitalist countries create an increased demand for raw materials and new outlets for the products. This should generate new international tensions and even some wars. At the domestic level, this economic growth also exacerbates the economic contradictions inherent to the capitalist system, and they therefore favour political unrest5 . In Kondratiev theory, wars, revolutions and territorial annexation are some consequences rather than the causes of the long economic cycles. They generally appear at the top of a rising phase; then the wars create destructions and unproductive consumption, therefore raising the demand for capital. This analysis is therefore fundamentally Marxist, what has not prevented the Marxist orthodoxy to reject it. Though N. Kondratiev introduced his works as Marxist, he was shot in 1938 after having been sent to Gulag. His long cycle's theory indeed contradicted the Leninist dogma, based on the idea of imperialism being the highest stage of capitalism. The major imperialist war that should occur thanks to increasing commercial and colonial tensions would allow proletarian revolutions in the most advanced capitalist countries6 . Kondratiev cycles' theory was judged as subversive, as it showed the capability of capitalism to overcome major economic crises. Many studies have later followed Kondratiev line, as the one of H.T. Davis in 1941 [START_REF] Davis | The analysis of economic time series[END_REF] , presented by V. Tarascio 8 . Davis' theory is based on the idea of fifty years' war cycles, the wars starting at the end of a long phase of commercial expansion and inflationist tensions, notably due to the increased demand for natural resources. Davis even calculates of war intensity coefficient, based on the difference between the prices' level in wartime and the average prices' level before the conflict. Contrary to Kondratiev, Davis presents a mutual interaction between war cycles and economic cycles.

I.2. Wars recessive effects

Since the origins of the liberal economic school, the cost of the war has been underlined [START_REF] Coulomb | Economic theories of peace and war[END_REF] . One of the most popular arguments is the one of the debt burden for the country when peace returns, if the war has been financed through loan, what seems unavoidable [START_REF]Sur ce point[END_REF] . Beyond the issue of public expenditures and related debt, the liberal economists present wars as being costly and counter-productive, because of human capital losses, of material destructions, of trade disruptions or of the rise in unproductive military staff. The works of J. Stiglitz and L. Bilmes 11 on the cost of the Iraq war present this conflict as a long-term economic burden for the American economy: the reflationary effect of this war would then be insignificant compared to its long-term recessive consequences. During the 1920-1945 period, several analyses of the link between wars and long economic cycles have developed, following Kondratiev works. Their conclusions are various, notably on the sense of the causality. Indeed, these studies remain very contingent and mostly suitable for the explanation of the 1930s economic crisis. Many studies have indeed focused on the role of monetary problems in causing recessions, after a major war. Like this, in his analysis of the economic consequences of the First World War, Hansen 12 explains the beginning of the declining phase of the economic cycle as being caused by the rapid succession of wartime inflation followed by peacetime deflation. Bernstein 13 also considers that monetary overvaluation is an explicative factor of economic depression in peacetime. In a longer-term perspective, J. Akerman [START_REF] Akerman | Structures et cycles économiques[END_REF] has presented the economic crises as a consequence of the war economy, and asserted that the economic cycles were created by political cycles. Akerman's analyses show that the changes in prices and interest rates precisely follow the war cycles. Wars' frequency is the determining factor of the long economic waves 15 . Though is the short run the war may create a rise in economic activity, in the longer run, the political and economic crises are positively related. According to F.G. Dickinson [START_REF] Dickinson | The economic costs of war[END_REF] , the First World War has created negative economic effects that may explain the interwar crisis. His statistical tests show the existence of long economic cycles and he predicts that the Second World War would have even more negative economic consequences, given the loss of flexibility of the domestic economy, following the rise in State interventionism. Other economists of this time have also underlined the problem of post-war reconstruction. According to J. Lescure [START_REF] Lescure | Principes d'économie rationnelle[END_REF] , the major wars (war of 1850/73 and the two world wars) create economic imbalance, as the demand for consumption and production goods increase with the conflict, until exceeding the supply, generating a rise in prices. The increase in production, prices and revenues due the State's use of war credit, durably disorganize the economy. When peace returns, a certain time will be necessary so that the imbalances on the various markets disappear. But a new difficulty will appear: the reconstruction create overcapacities, compared to a normal situation, as what happened in the 1920s.

All these analyses concerning the depressive economic effect of war have not been confirmed by the evolution of the world economy after 1945, which has known a phase of long growth. The reflationary effect of the reconstruction has been more important. The role of the new international monetary system and of the international organizations on the long-term economic growth may also have been important. The economic analysis of the link between the long cycles and major wars remains indeed very contingent: according to the countries and to the periods, the long-term economic consequences of wars may differ, as well as the influence of the economic context on these wars' outbreak.

I.3. War, military expenditures and crisis' end

In a Keynesian perspective, the war, or at least the war preparedness, may be efficient as a tool of economic reflation in a time of crisis. The Classical economist T.R. Malthus had already presented the economic interest of the war: while it allows containing the problem of overpopulation thanks to the human losses, it also creates a capital destruction that allows raising the effective demand, and therefore the level of the wealth 18 . However Malthus considered that these positive economic effects of the war would be cancelled by the negative consequences of State intervention: in wartime the public expenditures increase, notably because of the new aid given to the poor. These supplemental public expenditures encourage the population's growth, what is harmful for the national economic growth in the long run. These ideas are to be compared to the ones of J.M. Keynes, who besides much admired his predecessor. In 1939, Keynes suggests that governments sustain the demand through the multiplier mechanism 19 : the military expenditures are presented as one of the possible tools. Making the hypothesis of a rise in military expenditures of 150 millions pounds sterling, he forecasts the creation of 300.000 jobs, as well as a rise in consumption given the subsequent rise in revenues. However, the increase in arms production is only a lesser evil, as it doesn't meet the social needs and impedes in the long run the economic development's potential. The weapons being unemployed or destroyed in case of a war, the military expenditures are unproductive expenditures that send factors of production out of the economic circuit. The war's preparedness is a provisory stimulus to the economic activity but other public expenditures would be more socially useful, with longer term economic effects, as the public works. Keynes has besides asserted in 1942 that the fact that a country was forced by the international community to give up military expenditures would permit to accelerate its economic recovery and its industrial development 20 . According to him, Germany should therefore be asked to participate in collective peacekeeping operations in peacetime. The Keynesian perspective of the short or mid-term economic effects of war has been continued in the 1980s by J.K. Galbraith 21 , who shows the inertia effect of military expenditures. Less flexible downward than other public expenditure in a time of budgetary restrictions, they are also less flexible upward in a time of growth and overheating, the military expenditures growing less fast than other public or private expenditures. On contrary, in a time of depression, given the inertia effects of the defence sector (programs' are pluriannuelle and the personnel expenditures, little flexible, are important), these expenditures have a stabilizing effect. The defence budget would therefore be a stabilizing element of the capitalist economic systems, and notably of the American economy.

II -The current relation between economic cycles and major wars

If the debate on the link between economic cycles and major wars has been popular in the interwar period, it is less the case today, maybe given the lack of a major economic crisis comparable to the one of the 1930s or of a new world war. However the crisis of the 1970s (which end remains controversial), but also the Cold war, may be included in this debate, as well as the current Global War on Terror lead by the United States. But the economic analyses of the economic cycles after 1945 have been dominated by the concept of innovation, following the thought of J.A. Schumpeter. And yet, the link between major innovation and militarism has only been weakly studied. Moreover, the current analyses do not pay attention to the role of wars and/or of threat of war in the long-term economic changes. The economic consequences of the Cold war, that has lasted more than 40 18 Malthus T.R. (1986 [1836]), Principles of political economy, in The Works of Thomas Robert Malthus, edited by E.A. Wrigley and David Souden, London, William Pickering, vol. VI. 19 Keynes, J.M. (1939), "Will Rearmament Cure Unemployment?", The Listener, 1st June, in: D. Moggridge, ed., The Collected Writings of John Maynard Keynes, Volume 21. 20 Keynes, J.M. (1942), "Inter-Departemental Committee on Reparation and Economic Security", 21 December, in: D. Moggridge, ed., The Collected Writings of John Maynard Keynes, Volume 26. 21 Galbraith J.K. (1995 [1994]), Voyage dans le temps économique, Le Seuil, Paris, p. 264 (Original title : A journey through economic time. A firsthand view, 1994).

years, and the ones of the current American war on terror, may however have a long-term economic impact.

II.1. The complex link between economic cycles, major innovations and defence budgets.

After 1945, the economic analyses of long cycles have focused on the role of innovations and of the subsequent societal changes, without integrating possible military determinants. However the importance of military credits in the development of major innovations has been recalled by recent works.

 The legacy of J.A. Schumpeter

The Schumpetarian analysis is maybe the most famous explanation of the long economic cycles of capitalism. And yet, Schumpeter rejects the idea of significant externalities of militarism or war. He considers that the effect of the important increase in military expenditures before World War has been more recessive than reflationary for the economic activity 22 . He moreover doesn't recognize any role to wars in long-term econmoic cycles of capitalism 23 . The change in capitalism is due to the process of creative destruction, generated by the new products, new markets, new production techniques or new methods of industrial organization. These changes allow the permanent renewal of the industrial base, maintaining the capitalist economic dynamics. According to Schumpeter, the military sector and the wars cannot be considered as responsible for economic reversal, allowing the economy to emerge from a phase of depression and to benefit from growth. The wars are not presented as having a leading role in the capitalist system's changes : they may create conditions favourable for the industrial changes but at last, only the major innovations have a central role in the longterm capitalism's changes 24 . And yet the role of the military sector in the development of these major innovations isn't evoked. According to the economist, wars have not been decisive for the progress of capitalism. In the case of Germany for example, it's the customs union (Zollverein), more than the political unity coming from the war with France, that has favoured the economic development. The political actions, the wars, the territorial conquests and the conflicts for raw materials, have only had little impact on economic changes: only the technical progress are really determinant. And yet, while favouring the rise in interventionism and of bureaucracy, the wars make progressively disappear the spirit of capitalism and consequently the chances of major innovations development. Schumpeter therefore predicts that in the long-term, capitalism societies will be closer to the socialist model, what he regrets. Some contemporary analyses of the long-term changes in capitalism have considered innovations as central, notably the theory of endogeneous growth. The question may be raised to know if major wars favour the development of these major innovations.

* The role of military credits in the technological development

Opposite to the Schumpeterian theory is the idea according to which the military sector may be more liable than the private sector to make major innovations appear. Among the analysts defending this argument, the one of V.W. Ruttan25 is interesting. According to his study on the American case, the demand related to the defence sector has largely contributed to accelerate the learning process of new technologies. He more specifically studies the sectors of aeronautics, nuclear energy, computer industry, internet and space. In these sectors, the technological maturity, necessary so that the innovations generate productivity gains, would according to him have been more rapidly reached thanks to the demand of the military sector, very important notably during the two world wars and then the Cold war. As during the first half of the 19 th century, the rise in the electricity industry has been the main impetus to the rise in the global productivity for the American in the last decadres of the 20 th century the computer and the microprocessors have played the same role. These technologies have had an important reflationary effect. Ruttan's thesis is that only a threat of a major war could make emerge a new technology capable of rising durably productivity rates. The private sector will never be able to have the same role, as the related gains may be too weak and too diffuse to be captured by the firm that is engaged in the research, because of the slowness of the innovation's emergence, that may take some decades. This idea has been followed in many recent analyses on the long-term effect of the defence expenditure at the world level and of the growing privatization of military research and development 26 . Nowadays a large share of the production for the military sector is based on dual technologies. There is now an interaction between military and civil research. However the rise in the American military budget at the beginning of the 2000s has given important credits for the military R&D. The military sector being not concerned by the rules of the World Trade Organization, the public credits given to military projects may be considered as subsidies for the industry at large, and notably to the sectors of telecommunications and microtechnologies. The debate on the link between economic cycles and military expenditures therefore remains relevant today.

II.2. The Cold war, the Global War on Terror and the analysis of the economic cycles

The question of the bond between business cycle and major war can seem obsolete, if it is considered that since the end of the second world war, the probability of which has occurred of a new major war was reduced. But the Cold war can to a certain extent to be regarded as a major conflict, being given the broadth of the American and world military expenditure over the period 1948-91, with peaks related to the conflicts Korean and Vietnamese like with the revival of the arms race of the years 1980. Current the `total Guerre against terrorism' American also has a width resulting from the convergence of several minor conflicts (Iraq, Afghanistan), which will be able perhaps in the long term to lead the historians to qualify it major war. The evocation of the economic consequences of these two conflicts is thus interesting for our study.

•

The economic crisis begun in the years 1970 and it (future?) major war For certain economists, the economic crisis which struck the industrialized countries with the beginning of the year 1970 is still not completed. According to this theory, defended in particular per H. Patomäki, capitalism is always in the downward phase of a long cycle and the policy of the dominant power, the United States, would prevent any inversion of tendency, owing to the fact that it prevents reforming the international institutions effectively and from revealing novel modes of economic organization. A world war could in the long term result from this world economic crisis, because of progressive aggravation of the international tensions. Such an approach seems to us however contestable because it removes any direction with the concept of economic crisis. The United States profited during the Nineties from rates of economic growth without precedent, higher than those of the boom of the Fifties and The other industrialized countries also obtained comfortable growth rates during the Nineties, and the level of total wellbeing of the populations increased. Several countries of the South caught up with part of the delay which separated them from the countries of North, in terms of income per capita. To consider that capitalism still did not leave the economic crisis of the Seventies thus does not seem us not justified. The idea that only a world war could reverse the tendency seems also contestable, the more so as the cold war can be regarded as having been a major and world conflict. The question of its economic impact thus deserves to be studied.

•

The difficult estimation of the economic influence of the Cold war The economic impact of long run on the capitalist economies of the cold war and the American-Soviet arms race is difficult to interpret. There is no bond between the evolution of the world military expenditure since the years 1950 and that of the economic growth. If it is admitted that the worldwide economy entered a downward phase of a long cycle at the end of the years 1960, the question of the factor release arises: exhaustion of the model fordist according to the theory of the regulation, need to open new markets and new needs for consumption for the theorists for the innovation, but that can be also interpreted like the result of the aggravation of the cold war, at the time of the war of Vietnam. However the rise in the induced military expenditure on the level of the capitalist countries does not seem sufficient to have a significant economic impact. The israélo-Palestinian conflict also played a part, as a release of the oil crisis of 1973. But this conflict was not really integrated in the cold war and cannot be regarded as a major war. The end of the cold war on the other hand corresponded to a new phase of growth for the capitalist countries, and initially for the United States, which profited from growth rate without precedent of their GDP during the period 1992-2000, with a level of very weak unemployment. If it is admitted that world capitalism entered a phase of long growth to the beginning of the year 1990 (what is disputed by many economists), several factors in bond with the cold war can be proposed: long-term consequence of the revival of the public expenditure, mainly of the military expenditure, by the Reagan administration in the years 1980; benefit induced by fall of the military burden at the end of the cold war and the tax pressure decrease; rise of new markets related to the sector of communication and information technologies whose development was hastened by technological and military competition with the USSR. In addition, the statute of uncontested capitalist super power acquired by the United States because of their military supremacy their made it possible to obtain determining economic advantages: attraction of the overseas investments, imposition of the commercial opening to many countries, by the means of GATT and of the IMF, massive debt without important monetary depreciation, neither escape of the foreign assets, nor inflation. These positive effects of the cold war for the US economy raises the question of the real determinants of the arms race and the diplomatic confrontation with the USSR. But another point of view on the cold war is to consider that the US economy entered an inescapable phase of decline as from the years 1970, and that its recent domination was rather a domination by defect, because of the specific problems of Japan (crisis banking) and Germany (cost of the reunification). The analyzes of Galbraith defended of the arguments supporting this assumption and largely put in charge militarism growing in the exhaustion of the American model.

•

The `Global War on Terror': a burden or chance for the US economy?

The assumption can be made that the `total Guerre against terrorism' (Total War one Terror) started by the United States in 2001 with the invasion of Afghanistan, and continued by the war of Iraq begun in 2003, can in the long term be regarded by the historians as a major war. The American budget of defense indeed reaches levels similar to peaks of the cold war. The bond between the economic evolutions of long run and increasing militarism in the United States can be interpreted in two ways:

-Militarism and foreign operations help maintaining the American economic power: beyond the issue of oil supply and of research-development subsidies through the military budget, it's the role of the United States as an uncontested world superpower which is at stake today: the confidence in the American supremacy has an impact on the territorial attractiveness for foreign investors and so to capital inflows necessary for the economic growth and for the dollar's stability. It's also necessary for the efficiency of the soft power, that is, the diplomatic influence, useful to play on the international rules and economic agreements.

-The other hypothesis is that the militarism and the foreign operations are elements of an unelectable decline of the American economy, which is paralysed by the military burden, which high level is due to the role of the military-industrial lobby. Several analysts, among who J. Stiglitz, have criticized the economic cost of the Global War on Terror, notably because of the long-term burden of the social expenditures and of the public debt induced. More generally, the rise in the deficits may question the national economic model, which is characterised by an easy credit and households' over-indebtedness, leading to financial crises. This creates numerous subsequent problems, as the risk of an uncontrolled inflation or of the dependency towards other countries that own a part of the public debt. And yet, the role of the military expenditures in the growing indebtedness of the United States is important.

Conclusion

The economic analysis of capitalism's cycles became popular following Kondratiev works, as it allowed explaining the succession of phases of long growth and of economic crisis since the industrialization process. It is however less easy to identify the link with the major conflicts, as the war of 1850/73 or the two World Wars. The diversity of the elements to be considered so as to estimate the real economic impact of a war makes it difficult to show its long-term economic impact. Moreover, another explanation of the beginning of a rising phase of a long cycle has become dominant with time: the one of Schumpeter, who underlines the role of major innovations and who rejects the hypothesis of a link between major war and economic cycle. In the 1980s, the increased international competition with the growing trade interdependency, the financial globalization and the development of new economic powers, has definitely imposed the idea that innovation is at the heart of the capital system. The end of the Cold war and the spreading of the market economy's model seem to have removed all threat of major war to come. The issue of the link between economic cycles and major war therefore seems to belong to the history of economic thought. However, the current changes may lead to revise this idea: recent events have shown the structural tensions on raw materials' markets, due to the growing demand from emerging countries 27 . The destruction of industrial jobs in the richest countries favours domestic tensions, while environmental problems raise the threat of future international and civil conflicts, due to food shortage and subsequent migrations. Now the possibility of predation wars and of conflicts for the control of overseas resources reappears. Moreover, the hypothesis of a link between major innovation and major war or threat of war (as during the Cold war), remains relevant. Indeed, the military credits and the imperatives of the national defence have often allow to accelerate the development of innovations improving the productivity in the long-term, so the economic growth. Now, in the future, some new major threats will accelerate the development of revolutionary technologies that would open new markets, change the techniques of production, the modes of social organization, maybe opening a new long phase of economic growth at the world level. The research linked to environmental concerns may lead to such results, and it could be increased if some major ecological disasters would create new international tensions. But the economic analysis is not able to definitively show the link between economic cycles and wars or major threats for the world peace.

[START_REF] Kondratiev | The long waves in economic life[END_REF], "The long waves in economic life", The Review of Economic Statistics, 17 (Nov), pp. 105-115. Cet article est une présentation synthétique des travaux conduits par l'économiste russe dans les années 1920.

[START_REF] Tylecote | History as a forecasting tool : the future of the European economy in a long-wave/long-cycle perspective[END_REF], "History as a forecasting tool : the future of the European economy in a long-wave/longcycle perspective", Review of PoliticalEconomy, 4.2.,

 3 Modelski G. (1987), Long cycles in world politics, London,

Macmillan.4 Kondratiev N.D. (1935), op.cit.

La théorie deKondratiev (entre 1922Kondratiev (entre et 1928) ) sur la liaison entre les cycles de guerre et les cycles long est présentée de façon détaillée par Tarascio V.J. (1989), "Economic and war cycles", History of Political Economy, 21 (1), pp. 91-101.

[START_REF] Lénine | L'impérialisme, stade suprême du capitalisme[END_REF][START_REF] Lénine | L'impérialisme, stade suprême du capitalisme[END_REF]), L'impérialisme, stade suprême du capitalisme, Paris, Editions Sociales. Certains économistes marxistes de la période s'opposeront au déterminisme de cette analyse, expliquant

[START_REF] Schumpter | Business cycles: a theoretical, historical and statistical analysis of the capitalist process[END_REF], Business cycles: a theoretical, historical and statistical analysis of the capitalist process, New York, London, Mc Graw-Hill Book Co. Inc.

[START_REF] Schumpeter | The theory of economic development. An inquiry into profits, capital, credit, interest, and the business cycle[END_REF][START_REF] Schumpeter | The theory of economic development. An inquiry into profits, capital, credit, interest, and the business cycle[END_REF]), The theory of economic development. An inquiry into profits, capital, credit, interest, and the business cycle, Cambridge, Harvard University Press.

[START_REF] Schumpeter | Capitalisme, socialisme et démocratie[END_REF][START_REF] Schumpeter | Capitalisme, socialisme et démocratie[END_REF]), Capitalisme, socialisme et démocratie, Paris, Editions Payot.

[START_REF] Ruttan | Is war necessary for economic growth ? Military procurement and technology development[END_REF], Is war necessary for economic growth ? Military procurement and technology development, New York, Oxford University Press.

Voir notamment[START_REF] Bellais | Le rôle croissant du secteur privé dans la recherche-développement de défense : une mutation appropriée ?[END_REF], « Le rôle croissant du secteur privé dans la recherche-développement de défense : une mutation appropriée ? », Arès , 21 (53), 37-46.

Sur la question de l'aggravation probable des tensions Nord-Sud liées au commerce de biens énergétiques, voir[START_REF] Williams | Market cycles, power politics and the latest North-South energy-trade conflict[END_REF], "Market cycles, power politics and the latest North-South energy-trade conflict", Third World Quarterly,

(1), pp. 45-58.


Julien Pettré
email: jpettre@laas.fr

Jean-Paul Laumond

Thierry Siméon

3D Collision Avoidance for Digital Actors Locomotion

This paper presents some evolutions over the locomotion planning problem for digital actors. The solution is based both on probabilistic motion planning and on motion capture blending and warping. The paper particularly focuses on a new collision avoidance technique: while the legs and the pelvis of the digital actor follow a planned path, the animation of the upper part of the body is updated for 3D collision avoidance purposes.

I. INTRODUCTION

Computer animation for digital actors is usually addressed by two research communities along two complementary lines: Computer Graphics community puts emphasis on realism of the motion rendering [START_REF] Earnshaw | Computer animation for virtual humans[END_REF]. Realism can be obtained by motion imitation thanks to motion capture technologies. More recently, Robotics community tends to provide digital actors with capacity of action planning mainly in the area of motion planning (e.g., [START_REF] Koga | Planning motions with intentions[END_REF]).

This paper deals with combining both view points in the framework of virtual human locomotion. It focuses on the following problem: how to automatically compute realistic walking sequences while guaranteeing 3D obstacle avoidance?

An ef£cient approach consists in splitting the problem into two parts [START_REF] Kuffner | Goal-directed navigation for animated characters using real-time path planning and control[END_REF]. From the obstacle avoidance geometric point of view the digital actor is bounded by a cylinder. A 2D motion planner automatically computes a collisionfree trajectory for the bounding cylinder. Then a motion controller is used to animate the actor along the planned trajectory. Performances are good enough to address dynamic environments and real time planning.

Locomotion in 3D is investigated in [START_REF] Shiller | Planning motion patterns of human £gures using a multi-layered grid and the dynamics £lter[END_REF]: the workspace is modelled as a multi layered grid. Several types of digital actor bounding boxes are considered according to prede£ned locomotion behavior (walking, crawling...). Once a path is found in the grid, cyclic motion patterns are used to animate a trajectory along that path. The animation is then modi£ed by dynamic £lters to make it consistent.

Other similar approaches combining path planners and motion controllers have been investigated [START_REF] Raulo | Controlling virtual autonomous entities in dynamic environments using an appropriate sense-plan-control paradigm[END_REF], [START_REF] Reynolds | Steering behaviors for autonomous characters[END_REF], [START_REF] Choi | Planning biped locomotion using motion capture data and probabilistic roadmaps[END_REF]. None of these approaches addresses the 3D component of the locomotion problem as it is illustrated in Figure 1. In the absence of obstacle, all the degrees of freedom of a digital actor are controlled by the locomotion behavior (e.g., the cyclic motions of the arms are naturally induced by the walk). Walking with a bar in cluttered environments may require the actor to control the motions of his arms independently from the legs. How to reach such an objective with motions as natural as possible? Fig. 1. A locomotion plan in a living-room Our approach is an extension of [START_REF] Kuffner | Goal-directed navigation for animated characters using real-time path planning and control[END_REF]. A £rst collisionfree path is computed in the 2-dimensional world by using a classical path planner. Then the geometric path is transformed into a trajectory in order to apply a motion controller generating walking animation from a motion capture data set. Obstacle avoidance is taken into account at two distinct levels. The £rst planned path is guaranteed to be collision-free for the lower part of the actor body (i.e. the pelvis together with the legs). Then by applying the motion controller along that path, all the degrees of freedom of the actor are animated. Collision checking is then applied on the whole body. Only the upper parts of the body can be in collision. When collisions occur in subsequences of the animation, each of these subsequences is processed with a warping technique [START_REF] Witkin | Motion warping[END_REF]. The warping technique is applied only to the degrees of freedom to be corrected to avoid collisions. It just slightly modi£es the prede£ned animation on these degrees of freedom. In such a way the realism of the original animation is preserved at the best. If the warping step fails, then the original path is invalidated, and a new search is performed by the path planner.

The proposed approach is based on two-level modelling of our 57 degrees of freedom (d.o.f.) actor Eugene (Section II). The active degrees of freedom gather all the degrees of freedom attached to the legs: they are processed by the motion controller without any possible adaptation once a path is £xed. The reactive degrees of freedom gather all the other ones: they are attached to the upper parts of the body. Reactive d.o.f. are processed both by the motion controller and by the warping module. Section III presents the global architecture of the approach and summarizes the tools we have previously developed in this framework: the walk controller [START_REF] Pettré | Planning human walk in virtual environments[END_REF] as well as the path planner [START_REF] Siméon | Visibility based probabilistic roadmaps for motion planning[END_REF]. Section IV focuses on the warping technique which is the core module of the global system. Eugene is the name of our digital actor (Figure 2). He is made of 20 rigid bodies and 57 d.o.f. The pelvis is the root of £ve kinematics chains modelling respectively the arms, the legs and the spine. The pelvis is located in the 3D space with 6 parameters. Its location £xes the location of Eugene in the environment. All the remaining 51 d.o.f. are angular joints.

II. MODELLING EUGENE

Two classes of bodies are considered. Pelvis and the legs are responsible for the locomotion. All the 24 corresponding d.o.f. are said to be active d.o.f. The 27 other ones are said to be reactive d.o.f. They deal with the control of the arms and the spine.

Such a classi£cation is based on geometric issues dealing with obstacle avoidance. In the absence of obstacle, the walk controller (see below) has in charge to animate all the 51 angular d.o.f. along a given path. Due to the closed kinematic chain constituted by the ground, the legs and the pelvis, any perturbation on the active d.o.f. would affect the position of the pelvis, and then the given path. This is why we want the prede£ned path guaranteeing collision avoidance for all the bodies of the legs. Leg bodies and pelvis are then gathered into a bounding cylinder and the path planner (see below) computes collision-free paths for that cylinder. Possible collisions between obstacles and the upper part of Eugene are processed by tuning only the reactive d.o.f. without affecting neither the active d.o.f. nor the prede£ned path. Such a tuning is addressed by the warping module below.

III. PLANNING STEPS AND MODULES

The input data of the motion planner are a 3D environment, two (initial and £nal) con£gurations for Eugene and a walk controller allowing to steer Eugene along a prede£ned path. The output is an animated sequence showing Eugene walking to reach his goal while avoiding all the obstacles. The various steps are the following ones: The role of the warping module is to plan a collisionfree motion for the concerned reactive d.o.f. without changing the active ones along the subsequence of colliding key-frames. When the Warping module fails in computing a collision-free motion, the initial path computed at Step 1 is invalidated and a new path search is performed. The following modules have been implemented within Move3D [START_REF] Siméon | Move3d: a generic platform for motion planning[END_REF], a software platform dedicated to motion planning.

Path-Planner The £rst step deals with collisionfree path planning for a cylinder moving among 3D obstacles. This is a classical problem that can be solved by numerous approaches [START_REF] Latombe | Robot Motion Planning[END_REF]. The module we have implemented is based on a probabilistic roadmap approach [START_REF] Kavraki | Probabilistic roadmaps for path planning in high-dimensional con£guration spaces[END_REF]. A roadmap is a graph aimed to capture the topology of the con£guration space of a given mechanical system. Roadmap nodes are collision-free con£gurations. A steering method being given to compute a path between two con£gurations, two nodes are adjacent if the path computed by the steering method is collision-free. According to the symmetry property of the steering method, a roadmap is either a directed graph or an undirected graph. For our application (human locomotion) the computed path should be smooth enough. Bézier curves of the third degree are used. This gives rise to directed roadmaps, and the probabilistic roadmap builder was adapted to produce directed graphs.

Walk-Control The walk controller (see [START_REF] Pettré | Planning human walk in virtual environments[END_REF] for details) computes the values of all the degrees of freedom of the digital actor when applying a 2-dimensional control v¡ ω ¢ , v and ω being the linear velocity and the angular velocity respectively. This is the critical module that addresses the motion realism constraint. The controller is built on a motion capture library using a classical blending Fig. 3. Warping method steps technique [START_REF] Multon | Computer animation of human walking: a survey[END_REF], [START_REF] Rose | Verbs and Adverbs : Multidimensionnal motion interpolation using radial basis functions[END_REF], [START_REF] Wiley | Interpolation synthesis for articulated £gure motion[END_REF], [START_REF] Bruderlin | Motion signal processing[END_REF] consisting in merging recorded motion data to generate new animations. The output of this module is an animation buffer (i.e. sequence of key-frames).

Path-to-Traj The transformation of a path into a trajectory respecting velocity and acceleration constraints is a classical problem in Robotics (e.g., [START_REF] Renaud | Time-optimal motions of robot manipulators including dynamics[END_REF]). In our application the function of Path-to-Traj is to provide a sampling of the path into points x i ¡ y i ¢ compatible with the application of a control v i ¡ ω i ¢ . The following section presents the original Warping module we have developed to address 3D collision avoidance.

IV. THE WARPING MODULE

The goal of the Warping module is to locally modify the animation of the upper bodies of Eugene (arms and spine) when collision occur in the animation produced by Step 3. The output of Step 3 is a sequence of key-frames which a complete speci£cation of all the 57 d.o.f.

Each key-frame of the sequence is scanned and a collision test is performed. At this level only the bodies of the upper part of Eugene may be in collision. Leg bodies as well as pelvis are necessarily collision-free. If a collision exists, the frame is marked with a label (left-arm, right-arm or head-spine) according to the body involving a collision with the obstacles. All the marked frames are gathered into connected subsequences. Subsequences are extended to create blocks absorbing collision-free frames in the neighborhood of the colliding subsequences (Figure 3-a). Such a subsequence extension is considered to provide smooth motions able to anticipate the corrective actions to be done. Each connected frame block is then processed independently. Let us consider the example of a block with a left-arm label. The method consists in choosing a set of d.o.f. of the left arm at random until the left arm do not collide anymore. A new collision-free frame block is then created for which the d.o.f. of the left arm are modi£ed using this set of values (Figure 3-b). Now we apply a warping procedure considering the two blocks: the original and the modi£ed one. Such a procedure is classical in graphics to modify a sequence of key-frames. By construction the two blocks have the same number of key-frames. The warping procedure consists in interpolating the reactive d.o.f. of the left arm. The parameters of the interpolation are controlled by the collisionchecker in order to provide a new con£guration for the left arm which is as close as possible from the original con£guration while being collision-free (Figure 3-c).

V. RESULTS

Move3D, developed at LAAS-CNRS, has been used as support platform for implementing our method. This section presents some results obtained concerning the collision avoidance method described in the section IV. For legibility reasons, the results are illustrated with only few con£gurations. Exactly, one frame over three is used, over a small part of the whole computed animation. a) Careful with that branch, Eugene [START_REF] Waters | Careful with that axe, eugene[END_REF]: The £rst example is a human locomotion under a branch of a tree. The £rst image of the Figure 4 illustrates the result of the walk controller (i.e. when the trajectory is computed, optimized, sampled and animated). As expected, the lower part of the actor is collision free along the motion. But a collision occurs between the head and the branch; this is visible on the sixth con£guration drawn from the left.

The kinematic chain head-spine is detected in collision. The result of the warping procedure is illustrated on the second image at the bottom. Note that the new motion is realistic, and its amplitude is quite minimal. Also note that in this example, for one frame in collision, six are £nally modi£ed to avoid the obstacle. This correspond to the extension of the colliding subsequence into a block allowing an anticipation of the corrected motion. The actor has "decided" to move its hand in front of him while walking. Some other solutions exist. As the search of a solution is not deterministic, each execution of the method rise to different solutions. The arm could have pass over the barrier. There is no criteria to score a solution. The user estimates the quality of the result. He may call the warping module again to evaluate another solution. He may also impose the con£guration randomly chosen by the warping module. c) Careful with that chair, Eugene: Figure 6 illustrates that the model can be easily modi£ed for simulating the carriage of an object. The object does not Fig. 6. Avoiding a desk, handling an object in¤uence the result of the walk controller. But, as the bar is integrated to the right arm, the collision of the bar against the chair (see the left image of the Figure 6) is treated as explained previously. On the right image, a solution is illustrated: the bar goes over the chair and the desk.

d) Initial and £nal steps of a locomotion task:

Our walk controller has a speci£city: it respects strictly the initial and the £nal con£gurations given as inputs of the problem. This means that while starting or ending the locomotion, the actor progressively adopt those con£gurations.

In the case of the Figure 7, the actor is asked to feed the virtual sheep. For that its hand must go on the other side of the barrier. When the walk controller is applied, the £nal position (where the actor feeds the sheep) is respected but some collisions exist.

Then collisions are avoided. This leads to modify the motion of the arm. As it concerns the last frames in the animation, the £nal position is affected: the hand stays away from the barrier, and the actor cannot feed the sheep anymore. The result is illustrated on the middle image of the Figure 7. In order to still reach the £nal position, a single query probabilistic motion planner [START_REF] Kuffner | Rrt-connect : An ef£cient approach to single-query path planning[END_REF] is used between the last modi£ed con£guration and the £nal (and desired) con£guration. The result is then sampled and added at the end of the animation. The additive frames are illustrated on the bottom image of the £gure.

A more constrained example of the positioning problem is illustrated on the Figure 8. The goal position of the actor is de£ned with the arm passing through the hole of a plank. The actor walks until he is in front of the plank then he passes its left arm in the hole of the plank. Path-Planner steps are very shorts as the given problems do not need a complex navigation in the environments. The Path-to-Traj problem consumes more computing time. The complexity of this step is very sensitive to the constraints (maximum velocities and accelerations). The Walk-Control step only depends on the number of key-frames in the animation, as the same model is used.

Note that the Warping module is largely more expensive in the case of the Figure 6. This is due to the more complex environment (the living room), and to the high number of frames in collision (due to the carriage of the bar and the proximity of the chair).

A problem concerning the £nal step, in order to respect the position of the arm of the actor passing through the barrier, appears only on the example of the Figure 7. The computing time includes the single query path search, and its sampling.

VI. CONCLUSION

A solution for planning the locomotion of a digital actor through a virtual environment has been presented in this paper. The solution is based on a PRM motion planner, on a motion capture blender and on an collision avoidance technique. The method is demonstrated over several examples, with satisfying results. The inputs of the problem are precise con£gurations, possibly constrained, and paths through narrow passages can be found. The implementation of the method is modular and controllers can be added, removed or replaced to test different solutions.

At this stage, the locomotion is limited to a ¤at terrain, the lower part of the body is not reactive, and the solution to avoid an obstacle while walking is limited to a single sub-con£guration. These limitations give some directions for the work to come. For example, the lower part of the body should be reactive: some solutions are described in the literature ( [START_REF] Shih | Animation of human walking in virtual environments[END_REF]) and can be used as a base for a more sophisticated controller, allowing the walk on non-¤at terrains.

In a near future, we want to elaborate an intelligent strategy for constructing the initial roadmap. This could lead to more realistic trajectories with less optimizations on it, lowering the computing time. At last, the motion library needs to be extended with different types of walks (crawl, side steps, etc...). Our architecture can already mix several behaviors in a same plan but some adaptations are however needed to compute some transition phases. This would allow to £nd paths in even narrower passages.

Fig. 2 .

 2 Fig. 2. The digital actor: Eugene

1 )

 1 Plan a collision-free path for the cylinder bounding the legs and the pelvis: module Path-Planner, 2) Transform the path into a trajectory according to the velocity and acceleration bounds of the walk controller: module Path-to-Traj, 3) Animate Eugene along the trajectory: module Walk-Control. The animation appears as a sequence of key-frames. 4) Partition the animated sequence into alternate subsequences of collision-free key-frames and colliding key-frames. On each colliding subsequence apply the Warping module.

Fig. 4 .

 4 Fig. 4. Avoiding a tree branch

Fig. 5 .

 5 Fig. 5. Avoiding a wooden barrier

  e) Computational time: We give the computing times corresponding to the £gures of this paper. All the examples have been realized with a sampling rate of 25 frames per

Fig. 7 .Fig. 8 .

 78 Fig. 7. Feeding a sheep

Fig. 4 Fig. 5 Fig

 45 Fig. 4 Fig. 5 Fig. 6 Fig.7 # Total KF 85 64 53 69 PathPlanner 0£ 03s£ 0£ 05s£ 0£ 03s£ 0£ 04s£ PathToTraj 0£ 32s£ 0£ 22s£ 0£ 19s£ 0£ 34s£ WalkControl 0£ 1s£ 0£ 07s£ 0£ 05s£ 0£ 07s£ # Block KF 35 29 53 17 Warping 0£ 53s£ 0£ 23s£ 3£ 27s£ 0£ 28s£ Final Step 0s£ 0s£ 0s£ 0£ 62s£

Fig. 9 .

 9 Fig. 9. A locomotion plan through the sheeps

Figure 9

 9 Figure9illustrates a navigation problem. In this example an initial trajectory is found quickly (0£ 48s£ ). The Warping module computing time is essentially dedicated to the collision identi£cations (2s). Two blocks are formed: one for a collision against the sheep, another one against

VII. ACKNOWLEDGEMENTS

This work has been partly supported by the IST European Project 39250 MOVIE.

The environment of the living room in the example shown in Figure 1 and 6 has been provided by Daesign.

Thanks to F. Forges from Ex-Machina who gave us the motion capture data used in our examples. Some videos of the results are available at this web page: http://www.laas.fr/¤ jpettre/.

VIII. REFERENCES


Julien Pettré
email: jpettre@laas.fr

Jean-Paul Laumond

Thierry Siméon

A 2-Stages Locomotion Planner for Digital Actors

Keywords: motion planning, autonomous characters, probabilistic roadmaps, obstacle avoidance, locomotion control, motion capture

This paper presents a solution to the locomotion planning problem for digital actors. The solution is based both on probabilistic motion planning and on motion capture blending and warping. The paper describes the various components of our solution, from the first path planning to the last animation step. An example illustrates the progression of the animation construction all along the presentation.

Introduction

Computer animation for digital actors is usually addressed by two research communities along two complementary lines: Computer Graphics community puts emphasis on realism of the motion rendering [START_REF] Earnshaw | Computer animation for virtual humans[END_REF]]. Realism can be obtained by motion imitation thanks to motion capture technologies. More recently, Robotics community tends to provide digital actors with capacity of action planning mainly in the area of motion planning (e.g., [START_REF] Koga | Planning motions with intentions[END_REF]).

This paper takes advantage of both view points to address virtual human locomotion. It focuses on the following problem: how to automatically compute realistic walking sequences while guaranteeing 3D obstacle avoidance?

State of the Art An efficient approach consists in splitting the problem into two parts [START_REF] Kuffner | Goal-directed navigation for animated characters using real-time path planning and control[END_REF]]. From the obstacle avoidance geometric point of view the digital actor is bounded by a cylinder. A 2D motion planner automatically computes a collisionfree trajectory for the bounding cylinder. Then a motion controller is used to animate the actor along the planned trajectory. Performances are good enough to address dynamic environments and real time planning.

Locomotion in 3D is investigated in [START_REF] Shiller | Planning motion patterns of human figures using a multi-layered grid and the dynamics filter[END_REF]]: the workspace is modeled as a multi layered grid. Several types of digital actor bounding boxes are considered according to predefined locomotion behavior (walking, crawling...). Once a path is found in the grid, cyclic motion patterns are used to animate a trajectory along that path. The animation is then modified by dynamic filters to make it consistent.

Figure 1: Walking through the sheeps Other similar approaches combining path planners and motion controllers have been investigated [START_REF] Raulo | Controlling virtual autonomous entities in dynamic environments using an appropriate sense-plan-control paradigm[END_REF][START_REF] Reynolds | Steering behaviors for autonomous characters[END_REF][START_REF] Choi | Planning biped locomotion using motion capture data and probabilistic roadmaps[END_REF]]. None of these approaches addresses the 3D component of the locomotion problem. On one hand, the full integration of the animation process in a planning loop is time consuming. On the other hand, not considering the animation at the planning stage may lead to use bounding boxes, lowering the realism of the followed path (too far from obstacles, or even impossible in the case of narrow passages). Our objective is a realistic locomotion planner, both considering the quality of the motion and the quality of the followed path. How to reach such an objective with motions as natural as possible?

Architecture The method presented in this paper is an extension of [START_REF] Kuffner | Goal-directed navigation for animated characters using real-time path planning and control[END_REF]] and a continuation of the works introduced in [Pettré et al. n. d.]. It describes successively the main components of our approach. All of them are illustrated with the example presented in Figure 1 where the digital actor is asked to get out of a sheep-fold and to go in front of a wooden barrier, facing a sheep, and to feed it by passing his hand through the wooden barrier. The inputs of the problem are the 3D description of the environment and the two positions of the actor: the initial, standing in the sheep-fold; and the final one: facing the wooden barrier, feeding the sheep. All the bodies in the environment are considered as fixed obstacles to avoid.

The proposed approach is based on two-level modeling of our 57 degrees of freedom (d.o.f.) actor Eugene. Section 2 details the model: the active degrees of freedom gather all the degrees of freedom attached to the legs. The reactive degrees of freedom gather all the other ones: they are attached to the upper parts of the body; finally they are labeled with respect of the kinematic chain to which they belong.

A first collision-free path is computed in the 2-dimensional world by using a classical path planner described in Section 3. Then the resulting geometric path is transformed into a trajectory (Section 4). This step, similar to a sampling process, allows to adopt a classical animation data structure: a set of key-frames defining chronologically the successive positions of the actor. Our locomotion controller described in Section 5. It generates a walking animation from a motion capture data set.

Obstacle avoidance is taken into account at two distinct levels. The first planned path is guaranteed to be collision-free for the lower part of the actor body (i.e. the bodies with active degrees of freedom). Then by applying the motion controller along that path, all the degrees of freedom of the actor are animated. Collision checking is then applied on the whole body. Only the upper parts of the body can be in collision. When collisions occur in subsequences of the animation, each of these subsequences is processed with a warping technique presented in Section 6. It slightly modifies the predefined animation on the reactive degrees of freedom. In such a way the realism of the original animation is preserved at the best.

Finally, the initial and final positions given as inputs of the whole problem may not be respected due to the modifications to the animation introduced by the warping module. Section 7 shows how to add two planned motions at the beginning and at the end of the animation to the animation in order to respect those positions. Eugene is the name of our digital actor (Figure 2). He is made of 20 rigid bodies and 57 d.o.f. The pelvis is the root of five kinematics chains modeling respectively the arms, the legs and the spine. The pelvis is located in the 3D space with 6 parameters. Its location fixes the location of Eugene in the environment. All the remaining 51 d.o.f. are angular joints.

Modeling Eugene

Two classes of bodies are considered. Pelvis and the legs are responsible for the locomotion. All the 24 corresponding d.o.f. are said to be active d.o.f. The 27 other ones are said to be reactive d.o.f. They deal with the control of the arms and the spine.

Such a classification is based on geometric issues dealing with obstacle avoidance. In the absence of obstacle, the walk controller (Section 5) has in charge to animate all the 51 angular d.o.f. along a given path. Due to the closed kinematic chain constituted by the ground, the legs and the pelvis, any perturbation on the active d.o.f. would affect the position of the pelvis, and then the given path. This is why we want the predefined path guaranteeing collision avoidance for all the bodies of the legs. Leg bodies and pelvis are then gathered into a bounding cylinder and the path planner (see below) computes collision-free paths for that cylinder. Possible collisions between obstacles and the upper part of Eugene are processed by tuning only the reactive d.o.f. without affecting neither the active d.o.f. nor the predefined path. Such a tuning is addressed by the warping module (Section 6).

Path Planning

The objective of the Path-Planner module is to find a locomotion path through the environment between two given configurations of the actor. The locomotion path is an evolution of the position of the actor, thus it only deals with the position x, y of the actor and its orientation θ . The path ensures the collision-free motion of the lower part of the body, i.e. of its bounding cylinder.

The principle of this motion planning step is based on probabilistic roadmaps [START_REF] Kavraki | Probabilistic roadmaps for path planning in highdimensional configuration spaces[END_REF]]. The main idea of such motion planners is to capture the connectivity of the collision-free configuration space in a roadmap. In our case, nodes are collisionfree positions and edges collision-free local paths for the cylinder bounding the lower part of the body. Local paths are Bezier curves of the third degree.

As Eugene is assumed to go only forward, the planner computes a directed roadmap. Once the search is performed we get a first locomotion path which is guaranteed to smooth. This first path is then optimized by a classical dichotomy technique maintaining smoothness. As a result, the output of this step is a sequence of local paths: a continuous composition of Bezier curves, i.e. a B-Spline.

From Path to Trajectory

The module Path-to-Traj transforms the continuous parametric expressions of a 2D path into a discrete set of time stamped positions for the actor along the trajectory, respecting some criteria of maximal velocities and accelerations.

The 2D path is given by the Path-Planner module. It consists in a B-Spline: a continuous sequence of N Bezier curves. Thus, the position P(u) along the path is described by a parametric expression P(u) = [x(u), y(u), θ (u)] T , where u is a real number belonging to [0, N].

We want to introduce a time parameterization by sampling the path. The time scale defined by t i:0→m = i π where π is a constant number (the sampling period). Thus, we can then get a discrete time parametered expression of P : P(t i ) = P(u i )

We may introduce other discrete variables: v i and ω i respectively the tangential and the rotational speeds for each time step, with respect P(u i ), P(u i-1 ), and π. Also, the tangential acceleration a i (v i , v i-1 , π) is defined.

Additive variables are used to account for the following criteria: 1. u 0 = 0 and u m = N, 2. v 0 = 0 and v m = 0, 3. 0

< v i < V max , 4. -R max < ω i < R max , 5. -A max < a i < A max , 6. m is minimal.
where m is the necessary number of time steps to achieve the trajectory sampling. V max , R max and A max are user defined. The sampling rate, (i.e. the time period π) can also be defined.

The transformation of a path into a trajectory respecting velocity and acceleration constraints is a classical problem in Robotics (e.g., [START_REF] Renaud | Time-optimal motions of robot manipulators including dynamics[END_REF][START_REF] Lamiraux | From paths to trajectories for multi-body mobile robots[END_REF]). We do not develop the whole procedure. Note that always one of the previously defined criteria reaches its bound: the solution is optimal.

Locomotion Controller

The module Locomotion-Control transforms a set of time parameterized positions into a walk sequence. It is based on a motion capture blending technique. Therefore, it is composed of two elements: a motion capture library and a locomotion controller.

In order to solve a locomotion problem as illustrated on Figure 1, the library is filled with only one type of locomotion: the walk, grouping several similar motion capture examples. The similarity is estimated with respect of different criteria: same skeleton, same motion structure and same behavior (walking). So the difference between each motion cycle can be summered to the their average (tangential and rotational) speeds ( ṽ, ω) .

More precisely motion captures are expressed in the frequency domain using Fourier expansions. [x, y, θ ] parameters are modified as positioning errors around a virtual point moving at ( ṽ, ω). Such a transformation allows to make these parameters cyclic as the rest of the joint angles evolutions. Transformed variables are noted [∆x, ∆y, ∆θ ].

The input of the locomotion controller is the set of time stamped positions computed by the module Path-to-Traj. Thus, the parameters [P(t i ), v i , ω i ] of each time step t i are considered. A mo- tion blending formulae is computed for each time step, from which a motion cycle is created: MC t i . The characteristics speeds ( ṽ, ω) of MC t i are equal to (v i , ω i ).

A single configuration q i is the exctracted from MC t i . P(t i ) is considered to project q i on the followed trajectory. Projection is computed by adding [∆x, ∆y, ∆θ ] issued from MC t i , to the input parameters given by P(t i ). The other angular values are replaced. The extraction ensures the continuity of the motion between the frames i and i -1 and as a result, over the whole trajectory. Each key-frame of the sequence is scanned and a collision test is performed. At this level only the bodies of the upper part of Eugene may be in collision. Leg bodies as well as pelvis are necessarily collision-free. If a collision exists, the frame is marked with a label (left-arm, right-arm or head-spine) according to the body involving a collision with the obstacles. All the marked frames are gathered into connected subsequences. Subsequences are extended to create blocks absorbing collision-free frames in the neighborhood of the colliding subsequences (Figure 6-a). Such a subsequence extension is considered to provide smooth motions able to anticipate the corrective actions to be done. Each connected frame block is then processed independently. Let us consider the example of a block with a left-arm label. The method consists in choosing a set of d.o.f. of the left arm at random until the left arm do not collide anymore. A new collisionfree frame block is then created for which the d.o.f. of the left arm are modified using this set of values (Figure 6-b). Now we apply a warping procedure considering the two blocks: the original and the modified one. Such a procedure aiming at modifying a sequence of key-frames is a classical one in graphics [Witkin and Popovic 1995]. By construction the two blocks have the same number of keyframes. The warping procedure consists in interpolating the reactive d.o.f. of the left arm. The parameters of the interpolation are controlled by the collision-checker in order to provide a new configuration for the left arm which is as close as possible from the original configuration while being collision-free (Figure 6-c).

Figure 7 illustrates the result of the warping module, over the two parts illustrated in Figure 5 (output of the Locomotion-Control). Note that the realism of the motion is preserved, and that the movement allowing to avoid the collision is quite minimal. Our walk controller has a specificity: it respects strictly the initial and the final configurations given as inputs of the problem. This means that while starting or ending the locomotion, the actor progressively adopt those configurations.

Remember that in the case of Figure 1, the actor is asked to feed the virtual sheep. For that its hand must go on the other side of the barrier. When the walk controller is applied, the final position (where the actor feeds the sheep) is respected but some collisions exist. Then collisions are avoided by applying the warping module. This leads to modify the motion of the arm. As it concerns the last frames in the animation, the final position is affected: the hand stays away from the barrier, and the actor cannot feed the sheep anymore: see the middle image of the Figure 8.

In order to still reach the final position, a single query probabilistic motion planner [START_REF] Kuffner | Rrt-connect : An efficient approach to single-query path planning[END_REF] is used between the last modified configuration and the final (and desired) configuration. The result is then sampled and added at the end of the animation. The additive frames are illustrated on the bottom image of the Figure 8.

Discussion

The whole number of key-frames generated by the example of Note that computing times seem high, even if the machine used is weak. An effort is currently done to decrease the Path optimization computing times. Indeed, We use a generic and classical dichotomic method to optimize our path. The steering method for digital actors is quite particular, and should be optimized in a different manner. Also note that this is a development and non-optimized code.

More generally, computing times are sensitive to several elements. First, the complexity of the environment. The use of precomputed roadmaps allow to preserve the performance of the path search in the query phase. Nevertheless, environment complexity extends the time necessary to solve collisions in the warping module and to plan motions in the last positioning module.

The Figure 9 illustrates a more complex environment: a living room. To increase the complexity of the locomotion task, we added a long bar in the right hand of Eugene. This version of the model is named CWTB-Eugene (Careful with that bar Eugene [START_REF] Waters | Careful with that axe, eugene. Pink Floyd -Ummagumma[END_REF]). So the problem for CWTB-Eugene is now to handle a bar while crossing the living room. In order to avoid the desk, the piano and other furniture, CWTB-Eugene carries the bar in front of him. Different views appear in Figure 9. The more severe they are, the more this module is consuming. Also, the total number of frame is critical. Indeed, the Warping module will test the collision existence for each frame. Over more simple problems, such as illustrated on Figure 10, the whole result is obtained in less than a second.

Conclusion

We have presented a solution for digital actors locomotion problems. This paper insists on the modularity of the approach. Each component can be modified or replaced with ease. The example detailed along the paper illustrates the role of each component through the locomotion planning process and demonstrates the realism of the result.

Accounting for the 3D model of the environment is a specificity of our solution. Through our results, the navigation close to obstacles and their avoidance, thanks to little movements of the upper body, gives an illusion of a real interaction between the digital actor Our locomotion planner is still to be enhanced: we want to introduce the ability for the digital actor to change its locomotion behavior: by crouching, crawling, etc. This objective raises some new needs for our solution: the extension of the content of our motion library, the introduction of rules to change from a behavior to another. Some approaches of those problems exist in the literature. But a main part of our architecture is already designed to deal with such problems. Those enhancements are planned in our future works. Finally the scope of the approach at its current stage is restricted to walking tasks on flat floor. Future works will integrate rough terrains as well as stairs.

Figure 2 :

 2 Figure 2: The digital actor: Eugene

Figure 3 :

 3 Figure 3: A path made of 4 Bezier curves Our implementation is based on Move3D the motion planning platform developped a LAAS-CNRS [Siméon et al. 2001]. Figure 3 represents the path obtained for the problem illustrated on the Figure 1. The actor first surrounded by sheeps, navigates through them in order to get out of the sheep-fold, then pass under a tree branch to face the wooden barrier, just in front of the sheep.

Figure 4 :

 4 Figure 4: Characteristic profiles: v, ω and v Figure 4 illustrates the results of the Path-to-Traj step over the 2D-Path of the Figure 3. The v i and ω i speed evolutions are illustrated. The acceleration a i is displayed at the bottom figure.Note that always one of the previously defined criteria reaches its bound: the solution is optimal.

Figure 5 :

 5 Figure 5: Residual collisions

Figure 6 :

 6 Figure 6: Warping method steps

Figure 7 :

 7 Figure 7: Avoided branch and sheep

  Figure 8: Feeding a sheep

Figure 9 :

 9 Figure 9: Back home

Figure

  Figure 10: Skinning Eugene

Implementation has been done within Move3D platform [Siméon et al.

2001]. We used a Sun Blade 100 (proc. UltraSPARC-IIe 500 MHz, 768 Mo RAM)

Acknowledgement: The environment of the living room in the examples shown in Figure 9 and 10 have been provided by Daesign.


Julien Pettré

Thierry Simeon

Jean-Paul Laumond

Planning human walk in virtual environments

come


Isabelle Séverin

K Lionti

Laurence Dahbi

Bérangère C Loriot

Bérangère Toury

Marie-Christine Chagnon

Genotoxicity assessment of a polycarbonate sol-gel coating and its precursors intended to be used for food contact

RESULTS/DISCUSSION

Figure 1: The effect of GPTES on bacterial reverse mutation in the presence (+S9) or absence (-S9) of the rat liver S9 mix. (-), the vehicle control; (+), the positive control, in the absence of the S9 mix, 2-NF for TA 98, NaN3 for TA 100 and TA 1535, ICR 191 for TA 1537 and 4-NQO for WP2 (uvrA)pKM101, 2-AA for all the strains in the presence of the S9 mix. Coating:

Figure 2 :

 2 Figure 2:The effect of A8 formulation extract on bacterial reverse mutation in the presence (+S9) or absence (-S9) of the rat liver S9 mix. (-), the vehicle control; (+), the positive control, in the absence of the S9 mix, 2-NF for TA 98, NaN3 for TA 100 and TA 1535, ICR 191 for TA 1537 and 4-NQO for WP2 (uvrA)pKM101, 2-AA for all the strains in the presence of the S9 mix.

Figure 3 :

 3 Figure 3: MN and % of cytotoxicity data when the HepG2 cells were exposed to GPTES (mg/ml) with the S9 mix (4 h) (A) or without the S9 mix (24 h) (B). ** P < 0.01, significantly different from the negative control. Positive controls: cyclophosphamide (A) at 10 µg/ml and vinblastine sulfate (B) at 0.625 ng/ml.

  » LNC UMRU866, Nutox Team, Agrosupdijon, Université Bourgogne-Franche-Comté Dijon 21000, France, § IBM Almaden Research Center, San Jose, California 95120, USA, ⊥ Laboratoire National de Metrologie et d'essais, Trappes 78197, France, † Laboratoire des Multimatériaux et Interfaces UMR 5615, University of Lyon, Villeurbanne 69100, France . Polycarbonate (PC) is a widely used polymer in food packaging all around the world. However, due to the release of Bisphenol A, an endocrine disruptor during repeated washing cycles and certain physico-chemical conditions, its use becomes compromised. To solve this issue, sol-gel coatings based on organoalkoxysiloxane were developed for PC to act as a physical barrier. Common precursors, namely tetraethylorthosilicate (TEOS) and 3-glycidyloxypropyltriethoxysilane (GPTES), were used to prepare a sol-gel system (A8). These two chemicals, as well as the films obtained from the sol-gel systems were studied with regards to their potential toxicity in vitro. Our motivation for studying the toxicity of these precursors is to assess whether they are still present as traces in the final material, in case the polymerization step is incomplete and/or if the precursors are released during the packaging life time. Migration of extracts was measured and their genotoxicity was assessed using in vitro bioassays (Ames test and micronucleus assay). )pKM101 strains. The mutagenic effect was more pronounced in the presence of the exogenous metabolic activation system with an increase of the induction factor (ten-fold increase for the TA1535 strain) (Figure 1). This effect is certainly due to the chemical structure of GPTES with the presence of an epoxy group, which is a structural alert in genotoxicity (Ashby and Tennant, 1991).  In the micronucleus assay, GPTES gave negative results even in the presence of an exogenous activation system (Figure 3). Using regulatory battery of genotoxicity assays, only GPTES was positive in the Ames test. Migration of A8 formulation was the highest in the 10% ethanol simulant but under the regulatory overall migration limit (EU 10/2011). The sol-gel coating formulation is promising for food contact, but additional data, such as chemical analyses, or release study, are on the way to obtain the complete characterization of the extract and to claim A8 derived coatings as food grade materials.

Figure 4 :

 4 Figure 4:The MN and% of cytotoxicity data when the HepG2 cells were exposed to A8 formulation extract (µg/ml) with the S9 mix (3 h) (A) or without the S9 mix (24 h) (B). ** P < 0.01, significantly different from the negative control. Positive controls: cyclophosphamide (A) at 10 µg/ml and vinblastine sulfate (B) at 0.625 ng/ml.

Table 1 : Results of experimental migration for A8 formulation, expressed in mg/dm².

 1


E Souton

L Dahbi

T Nury

A Aljawish

I Séverin

M C Chagnon

Reliable bioassays to detect potential hazard of paperboard food contact material extracts

Food contact materials (FCM) represent a major economic issue and a large field of innovation. Food packaging production must be in compliance with the European Regulation 1935/2004: the third article specifies that FCM must not transfer their constituents to food in quantities which could endanger human health under normal or foreseeable conditions of use. Indeed, these materials are not inert and, in addition to started substances, Non-Intentionally Added Substances (NIAS) are able to be released into the food. NIAS can be contaminants from recycled materials, impurities, synthetic residues, new substances formed along the packaging production chain… Then, NIAS could represent a larget part of migrating substances which are not risk assessed, some being unpredictabled (Grob et al., 2006 ;Skejevrak et al., 2005). The European Regulation 10/2011 on plastic materials, multilayers and articles intended to come into contact with food regulates NIAS. It requires that the notion of the risk engendered by a substance concerns the substance itself, the impurities of this substance and any reaction or degradation products that are foreseeable in the context of the intended use. However there are currently no available guidelines to assess the risk of NIAS. They may also be present in other FCM than plastics, such as paper and boards... Because of the complex nature of FCM extract, it is pertinent to evaluate the potential toxicity of FCM as a whole taking into account any « cocktail effect ». The objectives of this study are to provide to packaging and food companies scientific relevant tools combining physicochemical and toxicological strategies based on bioassays applied to FCM extracts, especially paper and boards. Four toxicological endpoints were checked as relevant for low dose exposure: cytotoxicity, genotoxicity , oxidative stress and endocrine disruption activities.

Aqeous f

Figure 5 : 3 H-urindine uptake kinetics on HepG2 cells after 20 h exposure to all extracts of production chain. .

 Sensitive bioassay to detect and quantify DNA primary damage. H 3 -uridine uptake kinetics (NF EN 16418) Principle: Measuring the rate of incorporation of H 3 -uridine over time (30min) during the RNA synthesis in cells. Positive substances are able to decrease RNA synthesis kinetic (decrease >30%).

COMET ASSAY

 Positive control : 17β-estradiol (E2 1nM)

Cytotoxicity Genotoxicity

Comet assay: significant increase of primary DNA damages with two samples : the starting product and the frontbox. DCFDA assay: significant increase of fluorescence after treatment with each extract of the chain.

Endocrine disruption activities

-Estrogenic agonist activity of the starting product and the end product.

-Androgenic antagonist effects of the starting product, the grinder and the product of the end of the production chain. -Estrogenic antagonist and androgenic agonist activities of the extracts have been evaluated but none of the samples gave positive effects with these assays.

Figure 3 :

 3 Figure 3: Genotoxicity on HepG2 cells after 20h exposure to each extract of the production chain (2mg/mL). Three independent experiments; results + / -SEM; one sample t test to compare with theorical value of 100%, *p<0.05; ** p<0.01

Figure 6 :

 6 Figure 6: Normalized transcriptional activity relative to E2 1nM (natural reference agonist 17β-estradiol) after 20h exposure with different concentrations of the extracts of the production chain (tested doses: 1, 2.5, 5 and 10% in the treatment media; highest dose 10%: 2.5mg/mL) in the presence or not of the specific inhibitor of hERα (ICI 182,780: fulvestrant).One experiment; positive effect: transcriptional activity > 10% (red line).

Figure 1 Figure 2 :

 12 Figure 1 Sampling stations along the prodution chain (red circles), (adapted from lepapier.fr).

Figure 4 :Figure 5 :

 45 Figure 4: Percentage of DHE positive HepG2 cells after 20h exposure to the extracts of the production chain (2mg/mL). 10 000 events counted by flow cytometry). Five independent experiments; results + / -SEM; Mann-Witney test to compare samples with negative control, *p<0.05; ** p<0.01; ***p<0.001

Figure 7 :

 7 Figure 7: Normalized transcriptional activity relative to a suboptimal concentration of DHT 0.25nM (natural reference agonist 5αdihydrotestostérone) after 20h exposure with different concentrations of all extracts of the production chain (tested doses: 0.01, 0.1, 0.5, 1, 2.5, 5 and 10% in the treatment media; highest dose 10%: 2.5mg/mL). Two experiments; positive effect: transcriptional activity < 70% (red line).

  significant increase of the percentage of DHE positive cells induced by treatment with the tub (x4), grinder (x3), frontbox (x4) and end product (x4), except the starting product, compared to the negative control. Nevertheless, when taking into account the mean fluorescence (data not shown), the treatment with the starting product significantly increased this parameter in comparison with the negative control. Global strategy for the risk assessment of food contact materials ER Anti-AR Genotoxic effects of tested extracts observed with Comet assay may be due to oxidative stress induced by treatment with these extracts.