标题: 有偿翻译求助 [打印本页] 作者: leieryly 时间: 2007-5-6 10:55 标题: 有偿翻译求助 有些东西要翻译~大家帮帮忙~谢啦~要是有偿翻译可以私下商量~要是高手能无偿帮忙在下感谢万分~作者: leieryly 时间: 2007-5-6 10:56
MouseMotionListener classes’ methods to handle the various environment manipulation
tasks by the mouse: for instance, methods mousePressed() and mouseReleased()
(drawing, selecting), mouseDragged() (drawing, moving, resizing), mouseEntered()
and mouseExited() (signals entering and exiting from the canvas) and mouseMoved()
(highlighting shapes when mouse moves over it). While obstacles may overlap with
each other, the system forbids the robot to overlap (collide) with any obstacle. Collision is
an important issue that arises and requires computing the intersection of two shapes.When
the user chooses a goal point, this point represents the reference point of the robot, which
maps to be the left-bottom corner of the geometric shape of the robot. The new location
of the goal may be rejected if the area surrounding it can not accommodate the robot. This
type of verification, at this early stage, helps in eliminating undesirable degenerate cases,
which must be dealt with at a later stage in the path planning process. Notice that the Goal
button is enabled upon the creation of the robot. The objects’ geometric shapes should
be maintained convex. Thus, a validation module is implemented to check for convexity
of drawn objects. If a non-convex (i.e., concave) object is created, the module fixes it
by computing the object’s convex hull. Its use is an acceptable assumption and has been
widely used in the literature. Next, we present the algorithmfor computing the convex hull,
called Graham’s scan [1].
Algorithm ConvexHull(P)
Input: A set P of vertices for an object
Output: A list containing the vertices of CH(P) in CW order
1. Sort the points by x-coordinate, resulting in a sequence p1, . . . , pn
2. Put p1 and p2 in a list Lupper
3. for i ← 3 to n
4. do Append pi to Lupper
5. while Lupper has more than 2 points and the last 3 points do not
make right turn
6. do Delete the middle of the last 3 points from Lupper
7. Put the points pn and pn.1 in a list Llower
8. for i ← n . 1 downto 1
9. do Append pi to Llower
10. while Llower contains more than 2 points and the last 3 points
do not make right turn
11. do Delete the middle of the last 3 points from Llower
12. Remove the first and last points from Llower to avoid the duplication
where the upper and lower hull meet
13. Append Lupper to Llower, and call the resulting list L 14. return L
We first compute the convex hull vertices that lie on the upper hull, which is the part
of the convex hull running from the leftmost point p1 to the rightmost point pn when
the vertices are listed in a clockwise order. In a second scan, which is performed from
right to left, we compute the remaining part of the convex hull, the lower hull. Due to the
sorting step, the total time required for computing the convex hull is O(n log n). This is
one implementation of many others that have the same time complexity.
All objects in the environment are maintained in a vector called shapesVector. The Java
class Vector provides the capabilities of array-like data structures that can dynamically
resize themselves. This vector makes the input of the next phase.
The configuration space (C-Space) is the parameter space of the robot. A robot in
W-Space is represented by a point in C-Space, and any point in C-Space corresponds to
some placement of an actual robot in theW-Space [11]. The underlying idea of C-Space is
to represent the robot as a point called the reference point of the robot andmap the obstacles
into this space by growing their sizes by the size of the robot. The outer boundary of the
W-Space is considered as an obstacle and is mapped into the C-Space by enlarging it as
for other obstacles in the environment by the size of the robot. This mapping transforms
the problem of motion planning into the problem of planning the motion of a point. To
make this mapping possible, we use an efficient algorithm known as the Minkowski sum
algorithm [5].
Minkowski sums are a useful mathematical tool in the motion planning problem. Notice
that a very simple algorithm to compute the Minkowski sums of two convex polygons is
to compute v + w for each pair v, w of vertices, with v ∈ P and w ∈ R. Next, the convex
hull of all these sums is computed. The MinkowskiSums algorithm only looks at pairs of
vertices that are extreme in the same direction, which makes it run in linear time. In this
algorithm, the notation angle ( p, q) is used to denote the angle that the vector −→pq makes
with the positive x-axis. In order to perform the required computation, the lists of vertices
for any two convex polygons should be maintained in clockwise order, with the first vertex
in both lists as the smallest y-coordinate (and smallest x-coordinate in the case of ties).
The Minkowski sum algorithm runs in linear time, because at each execution of the
repeat-loop either i or j is incremented. One can observe that any vertex of the Minkowski
sum is the sum of two original vertices that are extreme in a common direction, and
the angle test ensures that all extreme pairs are found. So, the Minkowski sums of two
convex polygonswith n and m vertices, respectively, has O(n+m) time complexity. Fig. 5
shows the output of the Minkowski algorithm for a translating robot (polygon—leftmost
and topmost object in Fig. 4) (ignore the network of line segments for the time being).
Notice how the robot is shrunk to its reference point (i.e., bottom left corner) whereas each
obstacle including the outer boundary of theW-Space has been grown accordingly.
Algorithm MinkowskiSums(P, R)
Input: 2 convex polygons: P = {v1, . . . ,vn} and R = {w1, . . . ,wm}.
The vertices follow a CCW order, where v1 and w1 are the smallest.
Output: The Minkowski sums (P ⊕ R).
1. i = 1; j = 1
2. vn+1 = v1; wm+1 = w1
3. repeat
4. Add vi + wj as a vertex to P ⊕ R
5. if angle(vi vi+1) < angle(wjwj+1)
6. then i ++ 7. else if angle(vi vi+1) > angle(wjwj+1)
8. then j ++ 9. else i ++ 10. j ++ 11. until i = n + 1 and j = m + 1
The resulting set of C-obstacles will be stored in another vector as it will be extensively
used in the later phases.
5. Motion planning algorithms
5.1. The visibility graph
The visibility graph of a set of obstacles is more complex. It is the graph of all nodes
from all obstacles that can “see” each other. The edges formed must be external to the
obstacles. It has been proven that visibility graphs guarantee to compute the shortest path
because any shortest path between pstart and pgoal among the set S of disjoint polygonal
obstacles is a polygonal path whose inner vertices are vertices of S.
The above characterization of the shortest path enables us to construct the visibility
graph of S, denoted by Gvis (S). Its nodes are the vertices of S, and there is an arc
between vertices v and w if they can see each other: that is, if the segment vw does not
intersect the interior of any obstacle in S. Two vertices that can see each other are called
(mutually) “visible”, and the segment connecting them is called a “visibility edge”. This
also applies to the boundary—chain of line segments—of each obstacle. The endpoints of
each boundary segment (edge) are visible to each other. Hence, the obstacle edges form a
subset of the arcs of Gvis (S). The segments on the shortest path are visibility edges, except
for the first and the last segment. To make them visibility edges as well, the start and goal
positions are added as vertices to S; that is, the visibility graph will be considered of the set
S∗ = S ∪ {pstart , pgoal}. By definition, the arcs of Gvis (S∗) are between vertices (which
now include pstart and pgoal) that can see each other.
The visibility graph is implemented using the adjacency list approach. Adjacency
lists are linked lists, one list per vertex, that identify the vertices to which each vertex
is connected (i.e. the visible vertices to that vertex). All the vertices are stored in an
object of ArrayList, which is a dynamic array-class in Java. It is similar to the Vector
class. Each component of an ArrayList object, in the graph, contains a reference to a
linked list of edge nodes. Each node has a numeric index, a weight and a reference to
the next node in the adjacency list. Class AdjVertex encompasses these attributes. The
general specification of the implemented graph includes boolean methods for checking
whether the graph is empty (isEmpty()) or full (isFull()), and several methods to
add vertices (addVertex(vertex)) and edges (addEdge(from, to, weight)) and to
retrieve the vertices connected to a certain vertex (getToVertices(vertex)). Fig. 5
shows the visibility graphs in the C-Space. Next, we describe the general sketch of the
algorithm to compute the visibility graph.
Algorithm VisibilityGraph(S)
Input: A set S of disjoint polygonal obstacles including pstart and pgoal.
Output: The visibility graph Gvis (S).
1. Initialize the graph G = (V, E) where V is the set of all vertices of the
polygons in S and E = φ
2. for all vertices v in V
3. do W = VisibleVertices(v, S)
4. for every vertex w ∈ W,
5. do add the arc (v,w) to E
6. return G作者: leieryly 时间: 2007-5-6 10:56
If we want to test the visible vertices from a vertex, p, we have to check the segment pw
over all obstacles. We can use the information we get when we test one vertex to speed up
the test for other vertices. This can be accomplished by treating the vertices in cyclic order
whilemaintaining information that helps to decide on the visibility of the next vertex. Algorithm
VisibleVertices summarizes this operation. It first sorts the vertices by the clockwise
angle that the segment from p to each vertex makes with the positive x-axis. Vertices that
have the same angle are treated in order of increasing distance from p. The running time of
VisibleVertices is O(n log n). Because this method is to be applied to each of the n vertices
of S in order to compute the entire visibility graph, the visibility graph algorithm has an
O(n2 log n) time complexity, where n is the total number of obstacle edges. However, this
algorithm works only for disjoint convex polygonal shapes. In our system, this assumption
is very restrictive since we allow obstacles to overlap. Therefore, we modified the
algorithm to handle overlapping obstacles with O(n3) time complexity in the worst case.
5.2. Shortest path computation
Based on the visibility graph, the shortest path between pstart and pgoal is computed
using Dijkstra’s algorithm [5]. Dijkstra’s algorithm requires that each arc in the graph is
assigned a weight (the Euclidean distance of the arc connecting its incident vertices). Since
Dijkstra’s algorithm is to be used to find the shortest path between two points, pstart and
pgoal, we can stop the search process whenever the shortest path of pgoal is reached.
We use an auxiliary structure for storing vertices to be processed at a later stage.
We want to retrieve the vertex that is closest to the current vertex, that is, the vertex
connected with the minimum edge weight. If we consider minimum distance to be the
highest priority, the perfect structure to be used is the priority queue (minimum-heap).
Therefore, the algorithm utilizes a heap structure whose elements are the visible vertices
(edges) with the distance from the starting vertex pstart as the priority. The elements on the
heap are objects with three attributes: fromVertex, toVertex and distance. We use the class
PathNode to represent such objects. The basic operations defined for the priority queue
include enqueuing (enqueue(PathNade)) and dequeuing of objects (dequeue()), which
returns the highest-priority element from the priority queue, as well as testing for an empty
(isEmpty()) or full (isFull()) priority queue. The output of this algorithm is a list of
vertex pairs (edges) showing the total minimum distance from start vertex to each of the
other vertices in the graph, as well as the last vertex visited before the destination. Here is
the general outline of the algorithm:
Algorithm ShortestPath(Graph, pstart )
Input: Gvis (S∗) and the starting point pstart
Output: A list of vertex pairs that forms the shortest path from pstart to
every other vertex in the graph.
1. graph.ClearMarks()
2. Set the fromVertex and toVertex fields of a PathNode item to pstart
3. Set item.distance to 0
4. Enqueue item to priority queue (pq)
5. repeat
6. Dequeue an item from pq
7. if item.toVertex is not marked
8. then Mark item.toVertex
9. Save item to Path ArrayList
10. item.toVertex=item.fromVertex
11. item.distance=minDistance
12. Get vertexQueue of vertices adjacent from fromVertex
13. while more vertices in vertexQueue
14. do Get next v in vertexQueue
15. if v is not marked
16. then v=item.toVertex
17. item.distance=minDistance+ 18. graph.weightIs(fromVertex, v)
19. Enqueue item to pq
20. until pq becomes empty
21. return Path
where the “.” means the OO object membership. After determining the shortest path, the
robot can start navigating in theW-Space upon the user’s request. Robot motion along the
trajectory will be shown at discrete steps as depicted in Fig. 4 or 6. The discrete step is
controlled by the resolution parameter, which can be set by the user.
6. Simulation results and assessment
The system has been developed in Java. The AWT and Swing packages of Java provided
a rich collection of platform-independent components to create the system’s graphical user
interface and to handle mouse and keyboard events. Our system can run as an Applet or a
stand-alone application.
A user can easily set up or model a working environment via the control panel as in
Figs. 4 and 6. Both figures have dark objects (obstacles), a robot (light grey—polygon), and
a goal position (“+” sign). The computation of the C-Space is automatically displayed for
each environment upon request from the user. Fig. 5 shows the C-Space of the environment
in Fig. 4 (light shaded areas added to obstacles). This is a major computation before further
processing is performed. As depicted in Fig. 1, the visibility graph, the output of Dijkstra’s
algorithm and the shortest path are computed based on the computation of the C-Space.
This output result is shown in Fig. 5 too (it is the network of line segments connecting
some vertices, the start and the goal positions). Notice that, in actual simulations, different
colors are used to indicate the output of each phase. Once the shortest path is determined,
the robot starts navigating towards the goal in discrete steps as depicted in Figs. 4 and 6.
The robot may touch obstacles’ boundaries while navigating towards its goal. Therefore,
we added a new parameter, called safety, to control the clearance distance between the
robot and any obstacle’s boundary. Touching is allowed when the safety value is set to 0 as
can be noticed in both figures mentioned.
Usually safety is a major concern in robot motion planning: how close shall we allow
the robot to be to obstacles? Although it is a desirable feature, it could eliminate a possible
short path. One can argue that this is a price for safety. But what if the robot could not
find a path at all and reports failure, provided one exists. Since finding a path is our
major concern, then the system will adaptively re-adjust the safety value such that a path
is found. Fig. 4 shows a simulation where the shortest path is reported under a clearance
value = 4. Fig. 6, on the other hand, shows a new shortest path, for the same environment
as Fig. 4, after increasing the safety value to 5. This is because the previous shortest path,
among others, is eliminated from the visibility graph and, as a result, the system reports
the currently optimal one.
The proposed software system was appraised by junior, senior and graduate students
(35 students in total). Their comments provided useful feedback for improvement. The
appraisal was intended to investigate a number of key issues regarding the value of the
software as a Java-based CAL package for teaching purposes, which covers content,
presentation, effectiveness, suitability to audience, ease of use and interaction with the
interface. Results confirmed that the program is an extremely useful tool for teaching
and learning the graph structure and its algorithms. Students also showed a great deal of
satisfaction with the presentation, user interface and its ease of use. The outcome of this
assessment is depicted in Fig. 7. We intend to further evaluate this system over the next
two semesters before we accommodate any major changes, if any.
We believe that using Java in developing this system, with the enormous collection of
Java components, helped substantially in presenting complex modules in a more dynamic
and interactive manner. The use of Java as a language along with its desirable GUI support
provides a representation that is often better in communicating a concept than a static figure
or a written description. It also helps the students to visualize the basic concepts, whenever
possible, easily. Instructors can also gain by using such a tool. It will not only save their
time and effort but will also bring more realism to the subject matter by providing real-time
simulations.
This system creates an interactive environment of learning by experimentation. As a
result, such systems can increase motivation, instil greater interest among students and
encourage them to be more actively involved in the classroom.
7. Conclusion
Motion planning has been studied for several decades, and many motion planning
algorithms have been presented. Therefore, research in robot motion planning remains one
of the important fields of study in the task of building robot systems. Computation of a
collision-free path for a movable object (robot) among static obstacles is a fundamental
subject in the fields of robotics. It involves mapping obstacles from the working
environment into the configuration space, constructing the visibility graph and computing
the shortest path. We have presented a system, developed in Java, to trace visually the
output of each phase while computing the shortest path between two given points.
The system has been developed in Java. We chose Java because we want to make this
system accessible from the Internet. Such a system can be effectively used in a computerassisted
learning environment.作者: leieryly 时间: 2007-5-6 10:58
这是一个遗传算法的路径规划资料，其中有些算法和公式，机械方面的作者: jidiangf 时间: 2007-5-6 18:08
好长啊...作者: bravemanly 时间: 2007-5-6 22:22
可以给你翻译，并且保证质量和进度，不过要适当给点辛苦费哦。sdlkfj2
如果有需要请联系qq:460677641，注明:51testing.