DOC PREVIEW
MIT 16 412J - Study Notes

This preview shows page 1-2-3-27-28-29 out of 29 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Adaptable Mission PlanningforKino-Dynamic SystemsTony Jimenez,∗Larry Bush,†and Brian Bairstow‡May 11, 2005AbstractAutonomous systems can perform tasks that are dangerous, monoto-nous, or even imp oss ible for humans. To approach the problem of planningfor Unmanned Aerial Vehicles (UAVs) we present a hierarchical methodthat combines a high-level planner with a low-level planner. We pose theproblem of high-level planning as a Selective Traveling Salesman Problem(STSP) and select the order in which to v isit our science sites. We thenuse a kino-dynamic path planner to create a large number of intermediatewaypoints. This is a complete system that combines high and low levelplanning to achieve a goal. This pap er demonstrates the benefits gainedby adaptable high-level plans versus static and greedy plans.1 Introduction1.1 MotivationThe human control of robots on Mars is difficult, partially due to large com-munication lag times. One solution to this problem is to use robots capable ofautonomous activity. For unmanned aerial vehicles (UAVs), this capability isa necessity, since UAVs are constantly in motion and cannot stop and wait forinstructions. Thus, UAVs will need to be able to handle low-level planning, forexample the kinematics of getting from point A to p oint B.However, the question remains of how to handle higher-level planning, specif-ically, choosing which science sites to visit and in what order. The mission plancan be created on Earth and sent to Mars, or created by the UAV on Mars. Any∗Draper Laboratory, Cambridge, MA.†MIT Lincoln Lab ora tory, Lexington, MA.‡Massachusetts Institute of Technology, Cambridge, MA.1plan sent from Earth would essentially be a static plan, since re-planning wouldbe impossible because of the communication lag. This can be disadvantageousif the situation changes, for example if too much fuel is consume d or if newsensor readings show that a site is more interesting than previously thought. Ifthe mission planning is performed on the UAV or otherwise in-situ, then thepotential exists for response to changes in the environment. This can be im-plemented as continuous plan generation. Exploring the value that continuousplanning provides will give an idea of the magnitude and insights into when itis useful.1.2 Problem StatementOur scenario involves a UAV on Mars traveling be tween science objectives. TheUAV is given a set of interesting science sites and a limited amount of fuel. Theproblem is to guide the UAV to the science sites to gather as much science valueas possible within the fuel constraints.We address the design and analysis of an autonomous e xploratory plannerfor a UAV. This problem involves merging an adaptable mission planner with akino-dynamic path planner [1], and comparing the performance with that givenby a static plan. The mission planner will adapt to new readings of the sciencesites from a UAV’s long range sensors.1.3 Previous WorkOur project is premised upon two main bodies of work, namely that done by B.Hasegawa[2] and T. Leaute[1].1.3.1 Continuous Observation Planning for Autonomous ExplorationThe thesis by Brad Hasegawa presents a new approach for solving a roboticnavigation path-planning problem. The approach first formulates the problemas a selective traveling salesman problem (S-TSP), then converts it to an opti-mal constraint satisfaction problem and solves it using the Constraint Based A*algorithm. The solver, shown in the system architecture diagram in Figure 1,performs this key ability.The solver is a continuous observation planner, which updates the plan whennew observations affect the c andidate set (possible places to visit). The objec-tive of the robot is to map its environment. T he robot chooses to navigate toobservation locations, which will maximize information gain. Each observationmay affect the utility and cos t of unvisited observation locations (candidates),which necessitates re-planning. There is an implicit trade-off between the plan-ning horizon and how often the candidates are updated. The planning horizon2Figure 1: The above diagram is the system architecture for [2]. The navigationarchitecture starts with a partially complete map. Candidates and obstaclesare extracted from the map, which are used to construct a visibility graph. TheD* search is used to update the candidates. The candidates are passed to thesolver, which creates a plan (ordered candidate subset).3should mirror the expected time period between re-planning. In other words, ifwe look ahead 5 tasks, we want to be able to execute those 5 tasks before wehave to re-plan. If this does not occur, then our plan is optimized for a differ-ent planning period than it is executed for. This results in sub-optimal planning.Ultimately, the system is making an exploration-exploitation trade-off, whichcan be generalized to other tasks. The tasks must involve observation and can-didate list utility/cost updates. This method is likely to be effective when wehave (at a minimum) a large-scale prior map of the exploration region.The thesis [2] addresses a mapping application where the candidates fre-quently changed due to new observations. The finite-horizon technique is moreeffective when the candidates do not change frequently. Yet the mapping appli-cation actually favors observation c andidates that increase its situational knowl-edge the most. For these reasons, the finite-horizon method is more effectivewhen a high-level map is known. The attributes of continuous finite-horizonplanning lend themselves to exploratory missions with a specific objective (i.e.a science exploration application) where a prior map is known. R efining themap will affect the cost estimate for the science tasks and the utilities of thescience tasks may change as prior successes affect the probability of future suc-cesses. This necessitates continuous planning. However, the changes should besufficiently infrequent, so that a finite-horizon is more effective than a purelygreedy candidate selection strategy.Key elements of the framework presented in [2] are shown in Table 1.3.1.Table 1: Key attributes of the continuous observation-planning framework.Exploration Problem: Explore and construct a map of an environmentExploration Method: Feature basedAssumption: The robot knows the large-scale environment structurePath Cost: Path length (physical distance)Path Planner: Visibility Path Planner : F(map, candidates, pose)Map Type: Feature based SLAM mapPose: Robot position


View Full Document

MIT 16 412J - Study Notes

Documents in this Course
Load more
Download Study Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Study Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Study Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?