Novel Weighted A* Footstep Planner for Quadruped Robot Over Rough Terrain

Katherine Greatwood

Supervisor: Dr. Ioannis Havoutis

The development of quadruped robots has recently been an area of interest because of their ability to cross rough terrain which a wheeled robot cannot cross, and therefore their applications in policing, the military, and even planetary exploration. Planning the footstep locations across rough terrain is a difficult problem because there is a limited number of suitable footholds and a quadruped robot requires four footholds per pose. More work has been done on footstep planning for biped/humanoid (two legged) robots because fewer footholds (two) are required and therefore it is less computationally expensive and more likely to be efficient. Many quadruped planners plan the path of the body and simply place the feet underneath it, rather than carefully choosing footholds.

In this poster, a novel weighted A* footstep planner is presented for a quadruped robot over complex terrain. The environment is analysed and planes are identified which contain suitable footholds. Two versions of the planner are included. First, an offline version, which has prior knowledge of the environment and plans completely before moving. Second, an online version of the planner is presented, which has no prior knowledge and plans and moves at the same time. The online version is therefore able to react to changes in the environment.

The planner evaluates the quality of the footholds and tries to choose the highest quality footholds. The online planner uses a novel implementation of waypoints to allow the robot to plan and move simultaneously. Both versions were tested in a variety of simulated environments and are shown to be efficient and successful (no falls). In fact, the offline planner is as efficient as a similar biped footstep planner [1]. Therefore, the planner outlined in this poster is novel in its ability to plan footsteps (without planning of a basic body path) in complex terrain for a quadruped robot efficiently enough to be used in the real-world applications.

[1] Griffin, R. J., et al. (19 July 2019). Footstep Planning for Autonomous Walking Over Rough Terrain. 2019 IEEE-RAS 19th International Conference on Humanoid Robots (Humanoids). DOI:10.1109/humanoids43949.2019.9035046.

In this project we investigated two multi-agent non-cooperative games representing different electric vehicle charging problems. In both cases we considered the presence of uncertainty due to factors beyond agents control. One such factor could be the presence of renewables in the energy grid. This uncertainty was encoded through a data-driven scenario based approach, taking a finite set of samples and using these, without knowledge of the underlying probability distribution, in our optimisation. We have taken a worst-case approach by considering a maximum over these samples.

We also make use of previous work to produce a confidence bound on the probability that a new sample would lead to agents’ strategies being suboptimal. In playing these games we are interested in equilibrium concepts, in particular those developed by Nash and Wardrop.

The Nash equilibrium is useful since it allows us to define a set of strategies where agents are unable to unilaterally improve upon their individual cost. The Wardrop equilibrium is similar but now considers large populations for which individual agents’ strategies have negligible impact on the average strategy.

We have considered a number of different algorithms which could be applied to these games in order to find Nash and Wardrop equilibria, and have compared the equilibria found to a social optimum obtained when agents' strategies are optimised centrally.

We aim to provide a complete comparison of the different algorithms considered in order to provide information that could be useful in selecting algorithms for various use cases. In addition to this, we considered the possibility of taking a sampling-and-discarding approach to optimisation whereby we discard a number of the samples from our finite set in order to trade feasibility to robustness. We then have carried out numerical simulations to evaluate how effective this can be for our games..

A single¬-camera structure-¬from-¬motion solution to an important issue causing delays to overhead line electrified railways in the UK is presented. The issue entails misalignment between the train’s pantograph and the overhead contact wire, causing heavy wire dam¬age and requiring frequent or immediate shut down of the route for wire replacement.

Al¬gorithms are designed to reconstruct and track overhead lines in three-¬dimensional space using frames taken by the moving monocular carriage¬-roof-mounted camera monitoring the pantograph, drawing input from first principles in projective and multiview geometry to machine learning techniques applicable to image processing.

New methods to cali¬brate camera in physical dimensions, recover world coordinate from image points and identify and trace features across frames are introduced. The reconstruction algorithms are based on projective geometry and can be implemented robustly in real time on stan¬dard computing hardware.

The geometrical accuracy of the reconstruction algorithms are demonstrated with numerical and graphical examples. The design of an automated soft¬ware using the real time reconstruction to issue early¬-warnings to train drivers and prevent the occurrence of the misalignment issue is discussed. Also, the implication and future works of the single camera reconstruction results to depth perception, computer vision and robotics are explored.